Mr. Šikić, a chemistry teacher, is playing around with $n$ metal balls and $m$ copper wires. He joined together some pairs of balls with a wire so that all the balls are (directly or indirectly) linked to each other. He wants to teach his students about electric charge so he'll demonstrate it by charging the metal balls in a sequence.

Mr. Šikić can either charge each of the balls positively or negatively. When a ball is charged negatively, the electrons in all the wires connected to the ball are repulsed to the other ball connected to that wire. Conversely, if a ball is positively charged, the electrons from all the wires connected to that ball are pulled towards it. Charging the balls has the same effect on the wires irrespective of the wire's previous state.

At the beginning of the class, all the balls hold no charge and the electrons in all the wires are still. For every wire, Mr. Šikić has a specific direction of the electron flow in mind. Help him find a sequence of ball chargings that results in the desired electron flows.

Input Specification

The first line contains two integers $n$ and $m$ $(1\le n\le 200000,1\le m\le 500000)$ from the task statement.

The following $m$ lines contain integers $a_i$ and $b_i$ $(1\le a_i,b_i\le n,a_i\ne b_i)$ denoting that the balls $a_i$ and $b_i$ are connected by a wire and the electrons in the wire should be closer to $a_i$, and not $b_i$. There is at most one wire between a pair of balls. All the balls are directly or indirectly connected by wires.

Output Specification

If it is impossible to direct the flow of electrons according to Mr. Šikić's wishes, print -1. Otherwise, print $k$, the required number of ball chargings. $k$ must be less than or equal to $200000$.

In the following $k$ lines, print integers $c_i$ and $d_i$ $(1\le c_i\le n,0\le d_i\le 1)$, the number of the ball Mr. Šikić should charge in $i^{\text{th}}$ step and whether it should be charged positively (denoted by $d_i=1$) or negatively ($d_i=0$). If there are multiple solutions, print any one of them.

Constraints

Subtask	Points	Constraints
$1$	$15$	$1\le n\le 10$
$2$	$25$	$m=n-1$
$3$	$70$	No additional constraints.

Sample Input 1

3 3
1 2
2 3
1 3

Sample Output 1

3
2 1
3 0
1 1

Explanation for Sample Output 1

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

Now, we give ball $3$ a negative change. The arrangement of electrons between wires $2$ and $3$ remains unchanged, while the electrons on the wire between $1$ and $3$ are closer to ball $1$.

Finally, we give ball $1$ a positive charge. The wire between $1$ and $3$ remains unchanged, but on the wire between balls $1$ and $2$, electrons are now closer to ball $1$ and the desired arrangement is achieved.

Sample Input 2

4 3
1 2
3 2
2 4

Sample Output 2

4
2 1
4 0
3 1
1 1

Sample Input 3

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

Sample Output 3

-1