Campfire

Interview

Time limit1sMemory limit128 MB

Summary
Simulate campfire nights where Sunyoung's presence introduces a new song and other nights merge attendees' known songs, then output everyone who ends up knowing all songs.
Level

Medium4 of 10

Topics
Simulation, Hash map, Implementation
Solved
No attempts yet

Problem

Sunyoung and her friends went to the seaside for an E-day coding practice trip.

Every night there is a campfire. People who attend the campfire sing together, but attendance is optional.

Sunyoung's number is 1. On a night when Sunyoung attends the campfire, she creates a brand-new song and sings it. Everyone attending that night sings only that new song until the campfire ends, so all of them learn that song.

On a night when Sunyoung does not attend, the attendees share every song they already know with one another. Therefore, after that campfire, every attendee knows the union of all songs known by the attendees before it started.

Given the list of people who attend each campfire, find every person who knows all songs that appeared by the end of the trip, including Sunyoung.

Input

The first line contains the number N of people on the trip. People are numbered from 1 to N, and Sunyoung is person 1. (1 <= N <= 100)

The second line contains the number E of campfire nights. (1 <= E <= 50)

Each of the next E lines contains the number K of people attending that night's campfire, followed by the K attendee numbers. (2 <= K <= N)

Sunyoung attends at least one campfire.

Output

Print, in increasing order, the number of each person who knows every song at the end of the trip. Print one number per line.

Examples3

  1. Example 1

    Input
    4
3
2 1 2
3 2 3 4
3 4 2 1
    Expected output
    1
2
4

  2. Example 2

    Input
    8
5
4 1 3 5 4
2 5 6
3 6 7 8
2 6 2
4 2 6 8 1
    Expected output
    1
2
6
8

  3. Example 3

    Input
    5
3
2 1 3
2 2 1
4 2 1 4 5
    Expected output
    1