코난은 명의 사람 중 범인을 찾고 있다. 사람들에게는 번부터 번까지 번호가 붙어 있다.
각 사람은 다음 두 가지 성질을 가진다.
참말쟁이는 항상 참인 말만 하고, 거짓말쟁이는 항상 거짓인 말만 한다. 범인은 없거나 여러 명일 수 있다. 번 사람은 세상에서 가장 귀여운 밍구이므로 항상 참말쟁이이다.
총 개의 진술이 있다. 각 진술은 한 사람이 남긴 것이며, 진술의 종류 에 따라 다음 네 가지 중 하나이다.
진술 | |
|---|---|
"번 사람은 범인이 아니다." | |
"번 사람은 범인이다." |
모든 사람의 두 성질을 정한 것을 상태라 한다. 모든 진술이 진술한 사람의 성격과 모순되지 않는 상태를 가능한 상태라 한다. 즉, 참말쟁이의 진술은 모두 참이고, 거짓말쟁이의 진술은 모두 거짓인 상태이다.
가능한 상태가 무엇이든 관계없이 반드시 범인인 사람을 모두 찾으려 한다. 즉, 가능한 상태 전부에서 범인인 사람을 구한다.
첫 번째 줄에 정수 , 이 공백으로 구분되어 주어진다.
다음 개의 줄 중 번째 줄에 번째 진술을 나타내는 정수 , , 가 공백으로 구분되어 주어진다. 는 진술의 종류, 는 진술한 사람의 번호, 는 진술의 대상이 되는 사람의 번호이다.
가능한 상태가 존재하지 않는다면 첫 번째 줄에 -1을 출력한다.
그렇지 않다면 첫 번째 줄에 모든 가능한 상태에서 범인인 사람의 번호를 오름차순으로 공백으로 구분하여 출력한다. 그런 사람이 없다면 아무것도 출력하지 않는다.
"번 사람은 거짓말쟁이다." |
"번 사람은 참말쟁이다." |
입력은 다음과 같은 형식으로 주어진다.
