Bajtyna recently bought a toy from a suspicious website. Instead of receiving the well-known Tower of Hanoi puzzle, she found "Tower of Hanoj" in her mailbox.

The Tower of Hanoj consists of $m$ stacks, on which $n$ distinct blocks, numbered with integers from $1$ to $n$, are distributed. At the beginning of the game, and at every moment during it, the numbers of the blocks on each stack must be sorted in increasing order from the top to the bottom of the stack. In one move, a player can take the top block from any stack and place it on the bottom of any stack.

Bajtyna is now wondering what the minimum number of moves is required to place all blocks on the same stack. Help her solve this puzzle.

Input

The first line of input contains two integers $n$ and $m$ ($2 \le m \le n \le 10^6$), representing the number of blocks and the number of stacks, respectively. The stacks are numbered with integers from $1$ to $m$. The next $m$ lines contain descriptions of the stacks. The description of the $i$-th stack (for $1 \le i \le m$) consists of the numbers $k_i, v_{i,1}, \dots, v_{i,k_i}$ ($0 \le k_i \le n$, $1 \le v_{i,1} < v_{i,2} < \dots < v_{i,k_i} \le n$), where $k_i$ is the number of blocks on the $i$-th stack, and $v_{i,1}, \dots, v_{i,k_i}$ are the numbers of these blocks listed in order from the top to the bottom of the stack. All given blocks have distinct numbers in the range from $1$ to $n$, and each such block is located on some stack (i.e., $k_1 + \dots + k_m = n$).

Output

In the first line of the output, print a single integer $h$ representing the minimum number of moves required to solve the puzzle. In the following $h$ lines, provide descriptions of the consecutive moves. The description of the $i$-th move (for $1 \le i \le h$) should consist of two integers $a_i, b_i$ ($1 \le a_i, b_i \le m$), representing the transfer of the top element from stack $a_i$ to the bottom of stack $b_i$.

If it is not possible to solve the puzzle, print only a single line containing $-1$.

If there are multiple possible solutions, any one of them is sufficient.

Examples

Input 1

3 3
1 2
2 1 3
0

Output 1

3
2 3
1 3
2 3

Note 1

In the first test case from the example, we first move block $1$ from the top of the second stack to the empty third stack. Then we move block $2$ from the first stack to the bottom of the third stack. Finally, we move block $3$ from the second stack to the bottom of the third stack. In this way, at every moment of the game, the block numbers on each stack are sorted in increasing order, and after three moves, all blocks are on the third stack.

Input 2

7 3
4 1 2 5 7
1 4
2 3 6

Output 2

-1

Sample Tests

The sample tests include the examples above. Additionally:

• 0c: 10 blocks and two stacks, one of which is empty.
• 0d: 1000 blocks and three stacks, one of which is empty, and the other two contain blocks numbered with even and odd numbers, respectively.
• 0e: $10^6$ stacks and $10^6$ blocks, with one block on each stack.

Subtasks

If only the first line of your answer is correct, your solution will receive 50% of the points for the given test. You do not need to print the subsequent lines to receive these points.