만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

특별한 케이크

면접 대비

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

요약
학생 N명의 진술이 주어질 때, 나머지 학생은 모두 진실을 말하고 범인만 모든 진술이 거짓이라고 가정했을 때 범인이 될 수 있는 학생을 모두 찾습니다.
난이도

보통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에 등장하는 학생의 번호 S1,S2,⋯ ,SMS_1,S_2,\cdots,S_M이 중복 없이 공백으로 구분되어 주어진다.
  • 세 번째 줄에 진술의 유형을 나타내는 정수 BB가 주어진다. 범인이 있다는 진술이라면 B=1B=1, 없다는 진술이라면 B=0B=0이다.

출력

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

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

제한

  • 1≤N≤100 0001 \le N \le 100\,000
  • 1≤M≤N1 \le M \le N
  • 1≤Si≤N1 \le S_i \le N
  • 명단에 등장하는 학생 수의 합은 200 000200\,000을 넘지 않는다.

예제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