Hide

Problem D
Rock Band

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.

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

Please log in to submit a solution to this problem

Log in