바이러스

현대 정보학의 주요 과제 중 하나는 생물학적 과정을 모델링하는 것이다. 최근 생물학자들이 $n$개의 바이러스를 발견했다. 각 바이러스에는 1부터 $n$까지의 고유한 코드 번호가 붙어 있다. 바이러스는 다른 생명체의 세포에 침투할 수 있다.

처음에 세포가 $n$개 있으며, 번호는 1부터 $n$까지이다. 세포 $i$는 바이러스 $i$에 감염되어 있다. 각 세포는 한 번에 하나의 바이러스에만 감염될 수 있다.

각 세포는 바이러스마다 감수성 수준을 가진다. 세포마다 가장 감수성이 높은 바이러스, 그다음으로 감수성이 높은 바이러스 순서로 모든 바이러스가 주어진다.

감염된 세포들은 서로를 공격한다. 세포 $i$가 바이러스 $a$에 감염된 상태에서, 바이러스 $b$에 감염된 세포 $j$를 공격한다고 하자. 세포 $j$가 바이러스 $b$보다 바이러스 $a$에 더 높은 감수성을 가진다면, 세포 $j$는 바이러스 $a$에 감염된다.

실험에서는 $n$개의 세포를 모두 닫힌 환경에 넣는다. 세포들은 임의의 순서로 서로를 공격할 수 있다. 어떤 세포도 감염된 바이러스를 더 이상 바꿀 수 없으면 실험이 끝난다.

번호 $i$인 바이러스는 실험을 끝내는 어떤 공격 순서를 택하더라도 바이러스 $i$에 감염된 세포가 최소 하나 남으면 안정적이라고 한다.

번호 $i$인 바이러스는 실험을 끝내면서 바이러스 $i$에 감염된 세포가 최소 하나 남는 공격 순서가 존재하면 생존 가능하다고 한다.

예를 들어, 세포 1이 바이러스 1을, 세포 2가 바이러스 2를 가장 선호하면 어떤 공격도 상태를 바꾸지 못한다. 이때 두 바이러스 모두 안정적이며 생존 가능하다. 세포 1이 바이러스 2를, 세포 2가 바이러스 1을 가장 선호하면 공격 한 번 후에 실험이 끝난다. 이때 안정적인 바이러스는 없지만 두 바이러스 모두 생존 가능하다. 두 세포가 모두 바이러스 1을 가장 선호하면, 세포 2가 세포 1을 공격해도 변화가 없다. 세포 1이 세포 2를 공격하면 세포 2는 바이러스 1에 감염된다. 이때 바이러스 1은 안정적이며 생존 가능하고, 바이러스 2는 두 성질 중 어느 것도 없다.

세포의 설명과 질문 유형이 주어졌을 때, 안정적인 바이러스 또는 생존 가능한 바이러스를 모두 구하라.

첫째 줄에 바이러스와 세포의 개수 $n$ ($1 \le n \le 500$)이 주어진다.

다음 $n$개의 줄에는 각 세포의 설명이 주어진다. 각 줄에는 1부터 $n$까지의 서로 다른 정수 $n$개가 주어지며, 세포의 감수성이 높은 순서대로 바이러스 번호가 나열된다.

마지막 줄에는 정수 $p$가 주어진다. $p = 1$이면 안정적인 바이러스를, $p = 2$이면 생존 가능한 바이러스를 모두 구한다.

첫째 줄에 조건을 만족하는 바이러스의 개수 $k$ ($0 \le k \le n$)를 출력한다.

둘째 줄에는 그 바이러스들의 번호를 오름차순으로 출력한다.