Background

Translated from ROI 2018 Day1 T2. Вирусы (Viruses)。

Problem Description

There are $n$ cells and $n$ viruses. Initially, cell $i$ carries virus $i$. Each cell has a certain susceptibility to each virus.

Cells can attack each other. If cell A attacks cell B, and B's susceptibility to A's current virus is higher than B's susceptibility to its own virus, then B will be infected by A's virus (that is, B becomes a cell carrying A's virus).

The cells may arrange the attack order arbitrarily. The game ends if and only if no cell can be infected by any virus anymore.

If there exists an attack order such that virus $i$ finally has at least one cell, then virus $i$ is called a "feasible virus". If for every possible attack order, virus $i$ finally has at least one cell, then virus $i$ is called a "stable virus".

The viruses want to know how many feasible viruses and stable viruses there are.

Input Format

The first line contains a positive integer $n$, the number of cells and viruses.

The next $n$ lines each contain $n$ positive integers, describing the sequence of virus indices sorted in decreasing order of susceptibility in the current cell.

For example, if the input is 2 1 3, it means this cell is most susceptible to virus $2$, second most susceptible to virus $1$, and least susceptible to virus $3$.

The last line contains an integer $p$。

Output Format

The first line contains an integer $x$. If $p = 1$, output the number of stable viruses; if $p = 2$, output the number of feasible viruses.

The next line contains $x$ integers, the indices of these $x$ viruses in increasing order.

2
1 2
2 1
1

2
1 2

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

1
3

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

3
1 3 4

Hint

For all testdata, $1 \leq n \leq 500$。

Constraints

Translated by ChatGPT 5