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.
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 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.
Sample Input 1 | Sample Output 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 |
3 2 4 5 |
Sample Input 2 | Sample Output 2 |
---|---|
2 8 6 2 8 7 1 3 4 5 2 8 7 1 3 4 5 6 |
8 1 2 3 4 5 6 7 8 |
Sample Input 3 | Sample Output 3 |
---|---|
6 3 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 |
3 1 2 3 |