题目描述

译自 COCI 2021/2022 Contest #6 T3「Naboj」

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

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

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

输入格式

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

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

输出格式

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

接下来 $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$ 表示）。如果有多种方案，输出其中一种即可。

3 3
1 2
2 3
1 3

3
2 1
3 0
1 1

4 3
1 2
3 2
2 4

4
2 1
4 0
3 1
1 1

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

-1

数据范围与提示

对于全部数据，$1\le n\le 200\ 000, 1\le m\le 500\ 000,1\le a_i,b_i\le n,a_i\neq b_i$。

详细子任务附加限制及分值如下表所示。