Every day after school, you and your friends get together and play in a band. Over the past couple of months, the band has been rehearsing a large number of songs. Now it’s time to go out and perform in front of a crowd for the first time. In order to do so, a set list for the concert needs to be determined.

As it turns out, every band member has a different taste in music. (Who would have thought?) Everybody is very picky: a band member doesn’t want to play any particular song $X$ unless he also gets to play all songs he likes better than song $X$. This holds for every band member and for every song $X$. Furthermore, obviously at least one song should be performed.

The organisers of the concert do not want you to play too many songs, so a selection needs to be made that is as small as possible. As the unofficial leader of the band, you have taken it upon yourself to find a minimum length set list that meets the requirements.

-----Input-----
The first line contains two integers $M$ and $S$, satisfying $M \geq 1$ and $S \geq 1$ as well as $M\cdot S \leq 10^6$. These denote the total number of band members and the number of songs, respectively.

The following $M$ lines each contain $S$ integers per line, where the $i$-th line denotes the preference list of the $i$-th band member, starting with his favourite song and ending with his least favourite song. The songs are numbered $1$ through $S$.

No two band members have the exact same preference lists.

-----Output-----
Output the smallest possible set list, using the following format:
 - One line with an integer $L$: the length of the smallest possible set list.
 - One line with $L$ space-separated integers, denoting a sorted list of the songs to be played.

-----Examples-----
Sample Input 1:
3 8
4 5 2 1 6 8 3 7
5 2 4 8 6 1 3 7
2 5 4 8 1 6 3 7
Sample Output 1:
3
2 4 5

Sample Input 2:
2 8
6 2 8 7 1 3 4 5
2 8 7 1 3 4 5 6
Sample Output 2:
8
1 2 3 4 5 6 7 8

Source: kattis | Difficulty: MEDIUM
Tags: Data structures


Solutions: