COCI '06 Regional #1 Bard

View as PDF
Submit solution
Points: 7
Time limit: 0.6s
Memory limit: 32M
Problem type

Every evening villagers in a small village gather around a big fire and sing songs.

A prominent member of the community is the bard. Every evening, if the bard is present, he sings a brand new song that no villager has heard before, and no other song is sung that night. In the event that the bard is not present, other villagers sing without him and exchange all songs that they know.

Given the list of villagers present for E consecutive evenings, output all villagers that know all songs sung during that period.

Input Specification

The first line of input contains an integer N, 2 \le N \le 100, the number of villagers. The villagers are numbered 1 to N. Villager number 1 is the bard.

The second line contains an integer E, 1 \le E \le 50, the number of evenings.

The next E lines contain the list of villagers present on each of the E evenings. Each line begins with a positive integer K, 2 \le K \le N, the number of villagers present that evening, followed by K positive integers separated by spaces representing the villagers.

No villager will appear twice in one night and the bard will appear at least once across all nights.

Output Specification

Output all villagers that know all songs, including the bard, one integer per line in ascending order.

Sample Input 1

4
3
2 1 2
3 2 3 4
3 4 2 1

Sample Output 1

1
2
4

Sample Input 2

8
5
4 1 3 5 4
2 5 6
3 6 7 8
2 6 2
4 2 6 8 1

Sample Output 2

1
2
6
8

Sample Input 3

5
3
2 1 3
2 2 1
4 2 1 4 5

Sample Output 3

1

Comments


  • 0
    maxcruickshanks  commented on July 1, 2023, 2:57 a.m.

    Since the original data were weak, an additional two test cases were added, and all submissions were rejudged.


  • 1
    wildfireknits  commented on Feb. 26, 2023, 10:11 p.m.

    This is a little confusing because the problem does not state that the villagers do not have any songs until the bard teaches them one but that seems to be the case?