Problem Description

Mr. Šikić is a chemistry teacher. He is doing an experiment using $n$ metal balls and $m$ copper wires. He connects some pairs of metal balls with wires so that every ball is (directly or indirectly) connected to every other ball. He wants to teach students about electric charge, so he will demonstrate it by charging the metal balls one by one in some order.

Mr. Šikić can give each ball either a positive or a negative charge. When a metal ball is negatively charged, the electrons in all wires connected to that ball will be repelled toward the other metal ball at the other end of each wire. Conversely, when a metal ball is positively charged, the electrons in all wires connected to that ball will be attracted toward that ball. No matter what the previous state of a wire was, charging a ball has the same effect on the wire.

At the beginning of the class, all metal balls are uncharged, and the electrons in the wires do not move. For each wire, Mr. Šikić wants the electrons in it to end up closer to one fixed end, i.e., to have a specified direction. Please help him find an order of charging the metal balls so that in the end the electron direction matches what he wants.

Input Format

The first line contains two integers $n$ and $m$, with the meanings described above.

The next $m$ lines each contain two integers $a_i$ and $b_i$, meaning 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$ rather than $b_i$. Between any pair of metal balls, there is at most one wire. All metal balls are connected directly or indirectly through wires.

Output Format

If it is impossible for the final electron directions to match what Mr. Šikić wants, output $-1$. Otherwise, output $k$, the number of metal balls that need to be charged. It must hold that $k \leq 2\times 10^5$.

Then output $k$ lines. Each line contains two integers $c_i$ and $d_i \ (1 \leq c_i \leq n, 0 \leq d_i \leq 1)$, meaning that in step $i$ Mr. Šikić charges metal ball $c_i$, and $d_i=1$ means giving it a positive charge, while $d_i=0$ means giving it a negative charge. If there are multiple solutions, output any one of them.

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

Hint

Sample Explanation 1:

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

Now we give metal ball $3$ a negative charge. The wire between metal balls $2,3$ does not change, and the electrons in the wire between metal balls $1,3$ are closer to metal ball $1$.

Finally, we give metal ball $1$ a positive charge. The wire between metal balls $1,3$ does not change, but the electrons in the wire between metal balls $1,2$ are now closer to metal ball $1$, and the target directions are achieved.

Constraints:

For all testdata, $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 \neq b_i$.

The scoring of this problem is the same as in COCI 2021-2022#6, with a full score of $110$ points.

Translated by ChatGPT 5