题目描述

题目译自 CEOI 2022 Day2 T3「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$。

注意到最短解可能不唯一，你只需要输出任意一种即可。

4 5
1 0
2 0
1 3
4 4
3 2

3
5 2
3 5
3 1

4 5
0 0
2 1
3 1
3 4
2 4

-1

5 7
1 0
2 1
2 3
4 3
5 4
5 0
0 0

6
2 1
3 7
4 7
2 3
5 4
5 6

数据范围与提示

对于全部数据，$1\le N\le M\le 2\times 10^5$。

如果你的程序正确求出了最少的操作次数，但是方案构造错误，你将会获得对应点 $20\%$ 的分数。