P9001 [CEOI 2022] Parking

Valerija 在一家饭店的停车场工作，她负责礼貌地接待重要的客人，保管他们的车钥匙并帮助他们停车。 一个晚上，她发现她管理的停车场中恰好有 $2N$ 辆车，它们共有 $N$ 种不同的颜色，每种颜色恰有两辆车。我们将颜色按 $1$ 到 $N$ 编号。 停车场共有 $M$ 个车位，按 $1$ 到 $M$ 编号，每一个车位可以停下两辆车，一个车位只有一个入口，我们称靠近入口的为「顶上的车」，远离入口的为「底下的车」，一辆车可以从入口开出当且仅当没有车挡着它。Valerija 在停车的时候，保证每个车位要么空，要么停满两辆车，要么只有一辆底下的车。  这张图描述的是第一个样例，同时呈现了唯一的第一次驾驶。 Valerija 想要重新停放车使得每一对相同颜色的车都在一个车位里。我们并不关心车位对应什么颜色以及哪辆车在顶上哪辆车在底下。Valerija 将执行如下操作： - 驾驶一辆可以驶出车位的车，将车开到另一个车位，满足： - 这个车位是空的，并把车停在底下的车位，或者， - 这个车位有且只有一辆与当前驾驶的车颜色相同的车。 Valerija 想知道最少的操作次数与操作方案，请你解决这个问题。

第一行两个整数 $N,M$。 接下来 $M$ 行，一行两个整数 $b_i,t_i$，$b_i$ 表示停在这个车位底下的车的颜色，$t_i$ 表示停在这个车位顶上的车的颜色，如为 $0$，则表示这个车位底下/顶上的位置没有车。

如果没有办法完成要求，输出一行一个整数 $-1$。 否则，第一行一个整数 $K$，表示最少的操作次数。 接下来 $K$ 行，一行两个整数 $x_i,y_i$，表示第 $i$ 次操作将车位 $x_i$ 中可以驶出车位的车开到车位 $y_i$。 注意到最短解可能不唯一，你只需要输出任意一种即可。

### 样例 1 解释 由题目描述中的图可以看出，这个样例只有唯一解。 ### 数据规模与约定 对于全部数据，$1\le N\le M\le 2\times 10^5$。 如果你的程序正确求出了最少的操作次数，但是方案构造错误，你将会获得对应点 $20\%$ 的分数。 | Subtask 编号 | 特殊限制 | 分数 | | :----------: | :--------------------------------------: | :--: | | $1$ | $M\le 4$ | $10$ | | $2$ | $2N\le M$ | $10$ | | $3$ | $N\le 1000$，每个车位要么是空的要么是满的。 | $25$ | | $4$ | 每个车位要么是空的要么是满的。 | $15$ | | $5$ | $N\le 1000$ | $25$ | | $6$ | 无特殊限制 | $15$ |