특별한 케이크 (easy)

시간 제한1초메모리 제한1024 MB

요약
각 학생이 범인이 특정 명단에 있는지에 대한 진술을 할 때, 모순 없이 범인이 될 수 있는 학생을 모두 출력한다.
난이도

보통10점 중 4점

유형
완전 탐색, 구현, 시뮬레이션
정답자
아직 제출이 없습니다

문제

흐에에...

어둠을 틈타 누군가가 시이(swi)의 엄청난 케이크를 또 먹어버렸다!

여느날처럼 케이크를 좋아하는 시이는 근처 가게에서 사온 엄청난 케이크를 식탁 위에 올려놓고 감상하고 있었다. 하지만 기숙사 히터가 너무 따뜻했던 탓에 시이는 잠들고 말았고, 시이가 잠든 사이 케이크가 사라져버렸다!

케이크를 먹은 사람은 사건 당시 기숙사에 있던 시이와 시이를 제외한 NN명의 사람 중 한 명이다. 시이는 범인을 찾기 위해 자신이 자던 동안 기숙사에 있던 NN명의 학생을 동시에 추궁했다. 시이는 각 학생이 한 진술을 다음 두 종류의 유형 중 한 가지로 정리했다.

  • 명단 SS에 있는 학생 가운데 범인이 있다.
  • 명단 SS에 있는 학생 가운데 범인이 없다.

만약 NN명의 학생 중 한 명이 범인이라면 나머지 학생은 모두 범인을 알 것이므로 범인을 제외한 모든 학생은 사실대로 진술할 것이고, 범인은 자신이 케이크를 먹은 사실을 숨기기 위해 거짓으로 진술할 것이다. 그러나 NN명의 학생 모두가 범인이 아니라면 시이가 케이크를 먹어버린 것이기 때문에 모든 진술의 진위를 알 수 없다.

시이는 NN개의 진술을 바탕으로 범인일 가능성이 있는 학생을 추려내고자 한다. 어떤 학생이 범인이라 가정했을 때 NN개의 진술에 모순이 없다면 그 학생을 범인일 가능성이 있는 학생이라고 한다. 만약 NN명의 학생 가운데 범인일 가능성이 있는 학생이 없다면 소거법에 의해 시이가 범인이므로 swi를 출력한다.

입력

첫 번째 줄에 시이의 케이크가 없어졌다는 메시지 (swi's cake is missing!)가 주어진다.

두 번째 줄에 기숙사에 있었던 시이가 아닌 학생의 수 NN이 주어진다.

NN명의 학생의 증언이 각각 세 줄에 걸쳐 NN개 주어진다. ii번째 증언을 한 학생의 번호는 ii이다. 각 증언은 아래와 같은 형식으로 이루어져 있다.

  • 첫 번째 줄에 명단 SS에 등장하는 학생의 수 MM이 주어진다.
  • 두 번째 줄에 명단 SS에 등장하는 학생의 번호 S_1,S_2,⋯ ,S_MS\_1,S\_2,\cdots,S\_M이 중복없이 공백으로 구분되어 주어진다.
  • 세 번째 줄에 진술의 유형을 나타내는 정수 BB가 주어진다. 범인이 있다는 진술이라면 B=1B=1, 없다는 진술이라면 B=0B=0이다.

출력

모든 진술을 토대로 범인일 가능성이 있는 모든 학생의 번호를 작은 번호부터 순서대로 공백으로 구분하여 출력한다.

만약 범인일 가능성이 있는 학생이 한 명도 없다면 이번에도 시이가 케이크를 먹어버린 것이므로 swi를 출력한다.

제한

  • 1≤N≤101 \le N \le 10
  • 1≤M≤N1 \le M \le N
  • 1≤S_i≤N1 \le S\_i \le N

예제3

  1. 예제 1

    입력
    swi's cake is missing!
    2
    2
    1 2
    1
    2
    1 2
    1
    
    예상 출력
    swi
    
  2. 예제 2

    입력
    swi's cake is missing!
    2
    2
    1 2
    0
    1
    1
    1
    
    예상 출력
    1
    
  3. 예제 3

    입력
    swi's cake is missing!
    2
    1
    1
    0
    1
    2
    0
    
    예상 출력
    1 2