Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Defragmentation

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn this problem you have to implement an algorithm to defragment your hard disk. The hard disk consists of a sequence of clusters, numbered by integers from 1 to *n*. The disk has *m* recorded files, the *i*-th file occupies clusters with numbers *a*_{i, 1}, *a*_{i, 2}, ..., *a*_{i, ni}. These clusters are not necessarily located consecutively on the disk, but the order in which they are given corresponds to their sequence in the file (cluster *a*_{i, 1} contains the first fragment of the *i*-th file, cluster *a*_{i, 2} has the second fragment, etc.). Also the disc must have one or several clusters which are free from files.

You are permitted to perform operations of copying the contents of cluster number *i* to cluster number *j* (*i* and *j* must be different). Moreover, if the cluster number *j* used to keep some information, it is lost forever. Clusters are not cleaned, but after the defragmentation is complete, some of them are simply declared unusable (although they may possibly still contain some fragments of files).

Your task is to use a sequence of copy operations to ensure that each file occupies a contiguous area of memory. Each file should occupy a consecutive cluster section, the files must follow one after another from the beginning of the hard disk. After defragmentation all free (unused) clusters should be at the end of the hard disk. After defragmenting files can be placed in an arbitrary order. Clusters of each file should go consecutively from first to last. See explanatory examples in the notes.

Print the sequence of operations leading to the disk defragmentation. Note that you do not have to minimize the number of operations, but it should not exceed 2*n*.

Input

The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 200) — the number of clusters and the number of files, correspondingly. Next *m* lines contain descriptions of the files. The first number in the line is *n*_{i} (*n*_{i} ≥ 1), the number of clusters occupied by the *i*-th file. Then follow *n*_{i} numbers *a*_{i, 1}, *a*_{i, 2}, ..., *a*_{i, ni} (1 ≤ *a*_{i, j} ≤ *n*). It is guaranteed that each cluster number occurs not more than once and , that is, there exists at least one unused cluster. Numbers on each line are separated by spaces.

Output

In the first line print a single integer *k* (0 ≤ *k* ≤ 2*n*) — the number of operations needed to defragment the disk. Next *k* lines should contain the operations' descriptions as "*i* *j*" (copy the contents of the cluster number *i* to the cluster number *j*).

Examples

Input

7 2

2 1 2

3 3 4 5

Output

0

Input

7 2

2 1 3

3 2 4 5

Output

3

2 6

3 2

6 3

Note

Let's say that a disk consists of 8 clusters and contains two files. The first file occupies two clusters and the second file occupies three clusters. Let's look at examples of correct and incorrect positions of files after defragmentation.

Example 2: each file must occupy a contiguous area of memory.

Example 3: the order of files to each other is not important, at first the second file can be written, and then — the first one.

Example 4: violating the order of file fragments to each other is not allowed.

Example 5: unused clusters should be located at the end, and in this example the unused clusters are 3, 7, 8.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/15/2021 03:55:12 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|