시간 제한
메모리 제한
시간 제한
1초
메모리 제한
256 MB
학생 N명이 전략 게임 토너먼트에 참가한다. 참가자에게는 1번부터 N번까지 번호가 붙어 있다. 토너먼트가 진행되는 동안 남아 있는 참가자 중 임의의 두 명을 골라 경기한다. 진 사람은 탈락하고 이긴 사람은 계속 참가한다. 무승부는 없다. 총 N - 1번의 경기를 하면 마지막 한 명이 남고, 그 참가자가 우승한다.
일부 참가자 쌍에는 한 참가자가 다른 참가자를 항상 이기는 고정 승리 관계가 있다. 예를 들어 1번 참가자가 2번과 3번 참가자를 항상 이긴다면, 이 두 경기의 결과는 정해져 있다. 고정 승리 관계가 주어지지 않은 두 참가자가 경기하면 둘 중 누구든 이길 수 있다.
어떤 참가자에 대해 경기 순서와, 고정되지 않은 경기의 승자를 적절히 정해서 그 참가자를 최종 우승자로 만들 수 있다면 그 참가자는 우승 가능성이 있다고 한다. 특정 상대에게 항상 지는 참가자라도, 그 상대가 먼저 다른 참가자에게 탈락하면 우승할 수 있을 수도 있다.
N명의 참가자에 대한 모든 고정 승리 관계가 주어졌을 때, 우승 가능성이 있는 참가자를 모두 구하라.
첫째 줄에 참가자 수 N (1 <= N <= 100,000)이 주어진다.
다음 N개의 줄에는 각 참가자의 고정 승리 관계가 주어진다. 이 중 i번째 줄에는 먼저 정수 k_i가 주어지고, 이어서 i번 참가자가 항상 이기는 참가자 k_i명의 번호가 오름차순으로 주어진다.
자기 자신을 항상 이기는 관계는 주어지지 않는다. 고정 승리 관계의 총수는 1,000,000을 넘지 않는다.
첫째 줄에 우승 가능성이 있는 참가자 수 w와 해당 참가자들의 번호를 오름차순으로 공백으로 구분하여 출력한다.