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.