OpenKattis
Kattis Set 02

#### Start

2019-01-21 13:00 UTC

## Kattis Set 02

#### End

2019-01-28 09:29 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -373 days 6:47:35

164:29:59

0:00:00

# Problem HRock 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