题目描述

Šikić 先生是一位化学老师，他正在用 $n$ 个金属球和 $m$ 根铜导线做实验。他将一些对金属球用导线相连，使这些球（直接或间接地）与其他球都相连。他想要教学生关于电荷的知识，因此他将按顺序给金属球充电来演示它。

Šikić 先生可以让每个球带上正负电荷的一种。当一个金属球带负电荷时，与这个金属球相连的所有导线中的电子都将被排斥到与该导线相连的另一个金属球上。反过来，当一个金属球带正电荷时，与这个金属球相连的所有导线中的电子都将受这个金属球的吸引。无论导线的先前状态如何，给球充电对导线的影响都相同。

在刚上课的时候，所有的金属球都不带电，导线中的电子不动。对于每根导线，Šikić 先生都想让它其中电子的流向是某一个确定的方向。请帮他确定一个给金属球充电的顺序，使得最后电子的流向是他想要的。

输入格式

第一行两个数 $n$ 和 $m$，意义如题目描述。

接下来 $m$ 行每行两个整数 $a_i$ 和 $b_i$，表示金属球 $a_i$ 和 $b_i$ 之间有一根导线相连，并且这根导线中的电子应更靠近 $a_i$ 而不是 $b_i$。在一对金属球之间最多只有一条导线。所有的金属球都通过导线直接或间接相连。

输出格式

如果不可能让最后电子的流向是 Šikić 先生想要的，输出 $-1$。否则输出 $k$，表示需要充电的金属球数量。$k$ 必须小于等于 $2 \times 10^5$。

接下来 $k$ 行，每行输出两个整数 $c_i$ 和 $d_i$（$1 \le c_i \le n$，$0 \le d_i \le 1$），分别表示第 $i$ 步 Šikić 先生需要充电的金属球的编号和是给这个金属球充正电荷（用 $d_i = 1$ 表示）还是负电荷（用 $d_i = 0$ 表示）。如果有多种方案，输出其中一种即可。

样例

样例输入 1

3 3
1 2
2 3
1 3

样例输出 1

3
2 1
3 0
1 1

样例输入 2

4 3
1 2
3 2
2 4

样例输出 2

4
2 1
4 0
3 1
1 1

样例输入 3

5 10
2 4
3 4
1 4
4 5
3 2
2 1
5 2
1 3
5 3
1 5

样例输出 3

-1

数据范围

对于全部数据，$1 \le n \le 2 \times 10^5$，$1 \le m \le 5 \times 10^5$，$1 \le a_i, b_i \le n$，$a_i \ne b_i$。

本题共 20 个测试点，每个测试点 5 分，合计 100 分。

测试点编号	测试点数	数据范围
1 ~ 4	4	$n \le 10$，$m \le 20$
5 ~ 8		$n \le 1000$，$m \le 5000$
9 ~ 12		$n \le 10^4$，$m \le 5 \times 10^4$
13 ~ 16		$n \le 10^5$，$m \le 2 \times 10^5$
17 ~ 20		$n \le 2 \times 10^5$，$m \le 5 \times 10^5$