You have a graph with $n$ nodes and $m$ edges. Each node has a knob that you can turn clockwise or counterclockwise. Each knob can be in one of three positions: 0°, 120°, 240°. Initially, knob $i$ is in position $a_i$.

For each knob $i$ you also know its final position, $b_i$. You will need to find a way to turn knobs so that:

• in each step you turn only one knob (from one position to another position)
• two knobs that are connected by an edge are never in the same position
• after you are done, each knob is in its final position

Note that you can turn the same knob many times, to any of the positions.

Input

The first input line has two integers $n$ and $m$: the number of knobs and edges.

Then there are $n$ lines, each with two numbers $a_i$ and $b_i$. These indicate the current position $a_i$ and the final position $b_i$ of knob $i$.

Finally, there are $m$ lines, each with two numbers $i$ and $j$. This indicates that there is an edge between nodes $i$ and $j$; here $1 \le i < j \le n$.

The input configuration and the final configuration are valid: if there is an edge between knobs $i$ and $j$, then $a_i \ne a_j$ and $b_i \ne b_j$.

All inputs are such that if a solution exists, there is at least one solution with at most $10^5$ steps.

Output

If there is a way to turn knobs so that you can reach the final configuration, print a sequence that shows how to do it. First print one line with a number $s$ (at most $5 \cdot 10^5$): the number of steps. Then print $s$ lines, each with a pair of numbers, $x_k$ and $p_k$: in step $k$ you turn knob $x_k$ to position $p_k$. Here $1 \le x_k \le n$ and $p_k$ is 0, 120, or 240.

If there is no way to solve the problem, print only one line with value $-1$.

Constraints

• $1 \le n \le 20000$
• $1 \le m \le 20000$

Example

Input:

4 4
0 0
120 240
240 120
120 240
1 2
2 3
3 4
1 4

Output:

4
3 0
4 240
2 240
3 120

The following illustration shows the solution with four steps. Here 0° points up, 120° down right and 240° down left.