Valerija 在一家高档餐厅担任代客泊车员。她的工作是等待贵宾的到来，礼貌地迎接他们，获取车辆钥匙，并将车辆停放在附近的停车场。活动结束后，她要确保每位客人都取回了自己的车辆并愉快地离开。

一天晚上，在停好所有车辆后，她注意到关于车辆颜色的一项特别有趣的特性。停车场里总共有 $2N$ 辆车，它们共有 $N$ 种不同的颜色，每种颜色恰好有两辆车。我们将车辆的颜色用 $1$ 到 $N$ 的整数表示。

停车场本身由 $M$ 个停车位组成，编号为 $1$ 到 $M$，每个停车位最多可容纳两辆车。每个停车位只有一个入口，如果入口没有被其他车辆阻挡，车辆就可以进入或离开。我们将停在靠近入口处的车辆称为“顶层车辆”，将停在远离入口处的车辆称为“底层车辆”。Valerija 停车的方式使得每个停车位要么是空的，要么是满的（即包含两辆车），要么只包含一辆底层车辆。

第一个样例的示意图，展示了唯一可能的第一次移动。

Valerija 希望重新停放车辆，使得每对相同颜色的车辆都停在同一个停车位中。她不在乎哪个停车位包含哪种颜色，也不在乎具体哪辆车位于停车位的顶层或底层。她将通过一系列的“移动”来重新停放车辆。在每次移动中，她会坐进一辆能够离开当前停车位的车辆，并将其开往另一个停车位，该停车位必须满足以下条件之一： 是空的，在这种情况下，她将其作为底层车辆停放；或 包含一辆与她当前驾驶的车辆颜色相同的已停放车辆，在这种情况下，她将其作为顶层车辆停放。

Valerija 希望最小化重新停放车辆所需的移动次数。你的任务是帮助她找到实现目标的最短移动序列，或者确定不存在这样的序列。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $M$。

接下来的 $M$ 行中，第 $i$ 行包含两个空格分隔的整数 $b_i$ 和 $t_i$ ($0 \le b_i, t_i \le N$)，描述第 $i$ 个停车位。更具体地说，$b_i$ 表示底层车辆的颜色，$t_i$ 表示顶层车辆的颜色。如果停车位中的某个位置是空的，则对应的整数为 $0$。保证没有停车位只包含顶层车辆，即如果 $b_i = 0$，则 $t_i$ 也为 $0$。

输出格式

如果不存在能够按照 Valerija 的意愿重新停放车辆的移动序列，则在唯一的一行中输出 $-1$。

否则，第一行应包含一个整数 $K$，即满足 Valerija 目标所需的最少移动次数。

接下来的 $K$ 行中，第 $i$ 行应描述第 $i$ 次移动。它应包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le M, x_i \neq y_i$)，表示 Valerija 在第 $i$ 次移动中应将车辆从停车位 $x_i$ 开往停车位 $y_i$。当然，此时 $x_i$ 号停车位必须至少包含一辆车，且靠近入口的车辆必须能够移动到 $y_i$ 号停车位，即 $y_i$ 号停车位必须是空的，或者包含一辆颜色相同的车辆。

子任务

在所有子任务中，均满足 $1 \le N \le M \le 200\,000$。

如果你的程序在某个子任务的所有测试用例中都能正确确定最少移动次数，但对其中一些用例的移动描述输出错误（或根本没有输出），则该子任务将获得 20% 的分数。

样例

输入 1

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

输出 1

3
5 2
3 5
3 1

说明 1

任务描述中的图片描绘了此样例中停车场的初始状态。请注意，在这种情况下，每次移动都是强制的，即只有一次有效的第一次移动，只有一次有效的第二次移动，以及两次等效的第三次移动，之后我们达到最终目标。

输入 2

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

输出 2

-1

输入 3

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

输出 3

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