Problem Description

Mr. Šikić is a chemistry teacher who is conducting an experiment with $n$ metal balls and $m$ copper wires. He connects some pairs of balls with wires, ensuring that all balls are connected to each other either directly or indirectly. He wants to teach his students about electric charges, so he will demonstrate this by sequentially charging the metal balls.

Mr. Šikić can charge each ball with either a positive or negative charge. When a metal ball is charged negatively, the electrons in all wires connected to this ball will be repelled towards the other ball connected by that wire. Conversely, when a metal ball is charged positively, the electrons in all wires connected to this ball will be attracted by this ball. The effect of charging a ball on the wires is the same regardless of the previous state of the wires.

At the beginning of the class, all metal balls are uncharged, and the electrons in the wires are stationary. For each wire, Mr. Šikić wants the direction of electron flow to be in a specific direction. Help him determine a sequence of charging the metal balls such that the final direction of electron flow is as he desires.

Input Format

The first line contains two numbers $n$ and $m$, as described in the problem statement.

The next $m$ lines each contain two integers $a_i$ and $b_i$, indicating that there is a wire connecting metal balls $a_i$ and $b_i$, and the electrons in this wire should be closer to $a_i$ than to $b_i$. There is at most one wire between any pair of metal balls. All metal balls are connected to each other directly or indirectly through wires.

Output Format

If it is impossible to achieve the desired direction of electron flow, output $-1$. Otherwise, output $k$, the number of metal balls that need to be charged, where $k$ must be less than or equal to $200000$.

The next $k$ lines should each contain two integers $c_i$ and $d_i$ ($1 \leq c_i \leq n$, $0 \leq d_i \leq 1$), representing the number of the metal ball to be charged in the $i$-th step and whether it is charged with a positive charge ($d_i=1$) or a negative charge ($d_i=0$). If there are multiple solutions, output any one of them.

Sample Input and Output

Input Sample #1

3 3
1 2
2 3
1 3

Output Sample #1

3
2 1
3 0
1 1

Input Sample #2

4 3
1 2
3 2
2 4

Output Sample #2

4
2 1
4 0
3 1
1 1

Input Sample #3

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

Output Sample #3

-1

Notes

Sample Explanation 1:

First, we charge metal ball $2$ with a positive charge. The electrons in the wires between balls $1,2$ and $2,3$ are now closer to $2$. The wire between balls $1,3$ remains neutral.

Next, we charge metal ball $3$ with a negative charge. The state of the wire between balls $2,3$ remains unchanged, but the electrons in the wire between balls $1,3$ are now closer to ball $1$.

Finally, we charge metal ball $1$ with a positive charge. The state of the wire between balls $1,3$ remains unchanged, but the wire between balls $1,2$ now has electrons closer to ball $1$, achieving the desired flow direction.

Data Range:

For all data, $1 \le n \le 200000$, $1 \le m \le 500000$, $1 \le a_i, b_i \le n$, $a_i \neq b_i$.

This problem has the same scoring as in COCI 2021-2022#6, with a maximum score of $110$ points.

见题面 Input 部分

见题面 Output 部分