405882: GYM102147 D Viruses

D. Virusestime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

Modeling biological processes is one of the most important tasks in modern computer science. Recently, biologists have found $$$n$$$ viruses, each of which was assigned a unique code number from $$$1$$$ to $$$n$$$. A virus has the ability to integrate into the cells of other organisms. Initially, at the disposal of scientists, there are $$$n$$$ cells numbered from $$$1$$$ to $$$n$$$. The cell $$$i$$$ is infected with the virus $$$i$$$. Each cell can be infected with only one virus.

For each cell, the scientists know the level of susceptibility of this cell to each of the viruses, i.e. how easy it is for each virus to infect this cell. This is described by a permutation of code numbers of viruses.

Virus-infected cells can attack each other. If the cell $$$i$$$ is now infected with the virus $$$a$$$, it can be attacked by the virus $$$b$$$ from another cell, assuming that $$$b$$$ is before $$$a$$$ in the susceptibility permutation of the cell $$$i$$$. It doesn't matter from which cell the virus $$$b$$$ comes. As a result of such an attack, the cell $$$i$$$ becomes infected with the virus $$$b$$$.

For example, if the cell $$$i$$$ has permutation $$$(2, 3, 4, 1)$$$ and is now infected with the virus $$$1$$$, and some other cell $$$j$$$ is infected with the virus $$$3$$$, this virus can attack the cell $$$i$$$ – because $$$3$$$ is before $$$1$$$ in the permutation of the attacked cell $$$i$$$. After that, both cells $$$i$$$ and $$$j$$$ are infected with the virus $$$3$$$.

As an experiment, the scientists placed all the $$$n$$$ cells in a closed environment, causing cells to attack each other at random. The experiment ends when no virus can attack another cell anymore.

The scientists call the virus $$$i$$$ stable if it must survive the process, and they call the virus $$$i$$$ viable if it's possible it will survive the process.

More formally, the virus $$$i$$$ is stable if it remains in at least one cell at the end of the process after every possible sequence of attacks. The virus $$$i$$$ is viable if it remains in at least one cell at the end of the process after some possible sequence of attacks.

The scientists will want to know either which viruses are stable or which viruses are viable. Write a program that takes the description of the susceptibility of cells and the type of the question, and determines all the viruses with the given property (stable or viable).

Input

The first line of the input contains an integer $$$n$$$ — the number of viruses ($$$1 \le n \le 500$$$). This is also the number of cells.

The following $$$n$$$ lines describe the susceptibility of cells. The $$$i$$$-th line contains a permutation of numbers from $$$1$$$ to $$$n$$$ — the susceptibility permutation of the $$$i$$$-th cell.

The last line contains the number $$$p$$$ that specifies the property that is interesting for the scientists. The value $$$p = 1$$$ means you need to identify all stable viruses, while $$$p = 2$$$ means you need to identify all viable viruses.

Output

The first line of the output should contain an integer $$$k$$$ — the number of viruses with the given property ($$$0 \le k \le n$$$).

The second line should contain $$$k$$$ integers — the code numbers of viruses that have this property. The numbers should be displayed in ascending order.

Scoring

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \hline 1 & 11 & 1 \le n \le 5; p = 1 & \\ \hline 2 & 21 & 1 \le n \le 500; p = 1 & 1 \\ \hline 3 & 22 & 1 \le n \le 5 & 0, 1 \\ \hline 4 & 31 & 1 \le n \le 50 & 0 - 3 \\ \hline 5 & 15 & 1 \le n \le 500 & 0 - 4 \\ \hline \end{array}$$$$$$

You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.

ExamplesInput

2
1 2
2 1
1

Output

2
1 2 

Input

2
1 2
2 1
2

Output

2
1 2 

Input

2
2 1
1 2
1

Output

0

Input

2
2 1
1 2
2

Output

2
1 2 

Input

2
1 2
1 2
1

Output

1
1 

Input

2
1 2
1 2
2

Output

1
1 

Input

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

Output

1
3 

Input

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

Output

3
1 3 4 

Note

In two first sample tests, there are two viruses and the susceptibility permutations are $$$(1, 2)$$$ and $$$(2, 1)$$$ for the cell $$$1$$$ and the cell $$$2$$$ respectively. The virus $$$1$$$ is initially in the cell $$$1$$$ and it can't attack the cell $$$2$$$ (infected by the virus $$$2$$$) because the susceptibility permutation of the cell $$$2$$$ has the virus $$$2$$$ first. Similarly, the virus $$$2$$$ can't attack the cell $$$1$$$. The experiment is terminated immediately because no attack is possible. Hence, both viruses are stable and viable.

In the third and fourth sample, each of the two cells can be overtaken by the other virus. The experiment will end after one attack, and either the virus $$$1$$$ will be in both cells or the virus $$$2$$$ will be in both cells. No virus is stable, but both are viable.