시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 70 | 45 | 44 | 68.750% |
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 ≥ 1 and S ≥ 1 as well as M × S ≤ 106. 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:
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
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
6 3 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
3 1 2 3