A cycle $g : (q_1, q_2, q_3, \dots, q_k)$ is a one-to-one mapping from $\{1, 2, \dots, n\}$ to $\{1, 2, \dots, n\}$ that maps $q_1$ to $q_2$, $q_2$ to $q_3$, $\dots$, $q_k$ to $q_1$, and maps any integer not appearing in $q_1, q_2, \dots, q_k$ to itself. That is: $g(q_1) = q_2, g(q_2) = q_3, \dots, g(q_k) = q_1$, and for any $x$ not in $q_1, q_2, \dots, q_k$, $g(x) = x$.

The result of applying a cycle $g$ to a permutation $(p_1, p_2, \dots, p_n)$ of $\{1, 2, \dots, n\}$ is defined as: $g(p_1, p_2, \dots, p_n) = (g(p_1), g(p_2), \dots, g(p_n))$

For example, applying the cycle $(1, 3, 4)$ to the permutation $(3, 1, 5, 4, 2)$ results in the permutation $(4, 3, 5, 1, 2)$.

Given a permutation $(p_1, p_2, \dots, p_n)$ of $\{1, 2, \dots, n\}$ and a set of cycles, provide a method to transform this permutation into $(1, 2, \dots, n)$ using the minimum number of cycles. Each cycle can be used multiple times.

Input

This is an answer-submission problem. There are 10 input files named sort*.in in your directory.

The first line of the input file contains two integers $n$ and $m$, representing the length of the sequence and the number of available cycles, respectively.

The second line contains $n$ integers, which is the given initial permutation $(p_1, p_2, \dots, p_n)$.

The next $m$ lines each describe a cycle. The first number in each line is $k$, followed by $k$ integers $q_1, q_2, \dots, q_k$, representing the cycle $(q_1, q_2, q_3, \dots, q_k)$.

Output

For each input file, provide the corresponding output file sort*.out in the directory.

The first line of the output contains an integer $c$, representing the number of cycles used.

The next $c$ lines each contain an integer from $1$ to $m$, representing the index of the cycle used.

Subtasks

For each test case, if you provide no output, invalid output, or fail to transform the permutation into the target sequence, you receive 0 points.

For each data set, we have three scoring parameters $m_1, m_2$, and $m_3$: If $c \le m_1$, you receive 10 points. If $m_1 < c \le m_2$, you receive 5 points. If $m_2 < c \le m_3$, you receive 3 points. If $m_3 < c \le 1\,000\,000$, you receive 1 point. * If $c > 1\,000\,000$, you receive 0 points.

Among these, for the 8th test case: $m_1 = 2\,300, m_2 = 2\,400, m_3 = 3\,000$; For the 9th test case: $m_1 = 69\,000, m_2 = 75\,000, m_3 = 100\,000$; For the 10th test case: $m_1 = m_2 = m_3 = 1\,000\,000$.

Note

There is a program checker in your directory that can be used to test your output. You can use the following command in the terminal to check your output: ./checker N where $N$ is the test case number. For example, to test the 3rd test case, you can use: ./checker 3

This program will check if your output is valid. For valid output, checker will output "Right." Otherwise, it will output an error message.

Examples

Input 1

4 2
4 3 1 2
2 4 2
3 1 3 4

Output 1

2
2
1