化学老师 Šikić 先生正在用 $n$ 个金属球和 $m$ 根铜线进行演示。他用铜线连接了一些球对，使得所有球都（直接或间接）相互连通。他想向学生们传授关于电荷的知识，因此他将通过按顺序给金属球充电来进行演示。

Šikić 先生可以给每个球带正电或带负电。当一个球带负电时，连接到该球的所有铜线中的电子都会被排斥到与该铜线连接的另一个球上。相反，如果一个球带正电，连接到该球的所有铜线中的电子都会被吸引到该球。给球充电对铜线产生的影响与铜线之前的状态无关。

在课程开始时，所有的球都不带电，所有铜线中的电子都是静止的。对于每根铜线，Šikić 先生心中都有一个特定的电子流动方向。请帮助他找到一个给球充电的序列，使得最终达到期望的电子流动方向。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 200\,000$，$1 \le m \le 500\,000$），含义如题面所述。

接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$，$a_i \ne 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$），表示 Šikić 先生在第 $i$ 步应该给哪个球充电，以及应该带正电（用 $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 说明

首先，我们给球 2 带正电。此时，连接球 1 和球 2、以及连接球 2 和球 3 的铜线中的电子现在都更靠近球 2。连接球 1 和球 3 的铜线保持中性。

接着，我们给球 3 带负电。连接球 2 和球 3 的铜线中的电子排列保持不变，而连接球 1 和球 3 的铜线中的电子现在更靠近球 1。

最后，我们给球 1 带正电。连接球 1 和球 3 的铜线保持不变，但连接球 1 和球 2 的铜线中的电子现在更靠近球 1，从而达到了期望的排列。