Time limit
1s
Memory limit
256 MB
N students enter a strategy game tournament. The participants are numbered from 1 to N. While the tournament is running, any two remaining participants may be chosen to play a game. The loser is eliminated, and the winner stays in the tournament. There are no draws. After exactly N - 1 games, one participant remains and becomes the champion.
For some ordered pairs of participants, one participant is known to always beat the other. For example, if participant 1 is known to always beat participants 2 and 3, then those results are fixed. If no fixed relation is given for two participants, either participant may win their game.
A participant is considered able to become champion if there is some order of games, and some choice of winners for games without fixed relations, that leaves that participant as the final winner. Even if a participant always loses to one particular opponent, they may still become champion if that opponent is eliminated by someone else first.
Given all fixed win relations, find every participant who can become champion.
The first line contains the number of participants N (1 <= N <= 100,000).
Each of the next N lines describes one participant's fixed wins. On the i-th of these lines, first an integer k_i is given, followed by k_i participant numbers in increasing order. These are the participants that participant i always beats.
No participant is listed as always beating themself. The total number of fixed win relations is at most 1,000,000.
Print one line containing the number w of participants who can become champion, followed by their numbers in increasing order.