시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 63 42 2 50.000%

문제

봄캠프에 와서 공부하고 있는 월드인들의 공부 스타일은 도대체 어떤 스타일일까?

월드인들은 봄캠프 일과에 따라 낮에는 문제를 풀고, 밤에는 토론을 한다고 한다. 학생들을 너무나 사랑하는 김진영 조교는 오랜 분석을 거친 후에 월드인의 공부 스타일은 20X호의 네 명의 학생들의 유형으로 구분된다는 것을 알았다.

  1. ‘권○○’형 (kwon) : 낮에 문제를 풀 때도 열심히 하고, 밤에 토론을 할 때도 열심히 하는 모범적인 스타일. 매사에 열심이라서, 원장님께 항상 거짓말을 하지 않는 착하고 성실한 유형.
  2. ‘김○○’형 (kim) : 낮에 문제를 풀 때는 열심히 하지만, 밤에 토론을 할 때는 열심히 하지 않는다. 혼자 묵묵히 문제만 푸는 스타일이 되겠다. 따라서 낮에는 원장님께 거짓말을 하지 않지만, 밤에는 토론에 참여하지 않다 보니 찔려서, 자신도 모르게 거짓말을 하게 되는 유형.
  3. ‘이○○’형 (lee) : 낮에 문제를 풀 때는 별로 열심히 하지 않지만, 밤에 토론을 할 때는 열심히 참여한다. 코딩을 하는 것보다 말로 토론하는 것을 좋아하는 스타일. 따라서 낮에는 원장님께 거짓말을 하며 놀다가, 밤에는 잘못을 뉘우치고 거짓말을 하지 않는 유형.
  4. ‘한○○’형 (han) : 낮에 문제를 풀 때든, 밤에 토론을 할 때든 상관없이 열심히 하지 않는 스타일이 되겠다. 따라서 본의 아니게 낮과 밤을 가리지 않고 원장님께 족족 거짓말을 하게 되는 유형.

학생들의 스타일을 전혀 모르고, 지금이 낮인지 밤인지도 모르는 원장님께서 몇몇 아이들과 대화를 나누어 보고 있다. 원장님께서는 알려진 대로 “각 학생들의 공부 스타일은 도대체 어떤 스타일일까?”를 굉장히 궁금해 하신다고 한다. 학생들과의 대화 내용만을 가지고 지금이 낮인지, 밤인지, 문제를 푸는지, 토론을 하는지를 최대한 추론해야 한다. 물론, 모든 학생들은 다른 학생들의 스타일을 정확히 파악하고 있다고 하자.

대화 내용이 주어지면, 원장님을 도와 이 대화만으로 유추할 수 있는 정보를 모두 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1≤T≤10)가 주어진다. 각 테스트 케이스는 아래와 같은 형식을 따른다.

첫째 줄에 문장의 개수 N(1≤N≤100)이 주어진다. 이어서 N개 줄에 대화 내용이 입력되는데, 모든 대화는 화자의 이름과 그 뒤를 따르는 ‘:’으로 시작된다. 학생들의 이름은 A∼H 중 하나이다. 모든 대화는 아래와 같은 형식을 따른다.

  • I am [not] ( kwon | kim | lee | han | lying ).
  • ‘X’ is [not] ( kwon | kim | lee | han | lying ).
  • We are ( problem solving | discussing ).
  • It is ( day | night ).

여기서 [not]의 의미는 not이 나타날 수도 있고 나타나지 않을 수도 있다는 것이다. ()의 의미는 |으로 구분된 단어 중 하나는 반드시 나타나야 한다는 것이다. X는 A∼H 중 하나를 말한다.

출력

각 케이스마다 첫째 줄에 번호를 "#1"∼"#10"과 같이 출력한다.

만약 입력된 대화가 절대 일어날 수 없는 것이라면 "Impossible."을 출력한다. 가능한 대화이기는 하지만 입력으로부터 추론할 수 있는 사실이 아무 것도 없다면 "No idea."를 출력한다. 그렇지 않다면 추론 가능한 모든 사실을 출력해야 한다. 사실들은 다음과 같은 형식으로 출력한다.

  • ‘X’ is ( kwon | kim | lee | han)
  • They are ( problem solving | discussing )
  • It is ( day | night )

학생들의 정보는 A부터 H의 순서로 출력하고, 그 외의 사실들은 위의 형식에 나타난 순서대로 출력한다.

예제 입력

4
1
A: I am kwon.
2
A: I am lying.
B: It is night.
2
A: I am han.
A: We are problem solving.
4
A: B is lee.
B: A is han.
A: B is han.
A: B is kim.

예제 출력

#1
No idea.
#2
Impossible.
#3
A is kim.
They are discussing.
It is night.
#4
A is han.
B is kwon.

힌트

출처