문제1767--크리스마스 전구

1767: 크리스마스 전구

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB  Special Judge
제출: 95  통과: 19
[제출] [채점기록] [묻고답하기]

문제 설명

류주는 올해 크리스마스도 여전히 혼자 놀 것을 예상하고 미리 크리스마스 준비에 착수했다. 왜 벌써부터 준비하냐고 묻는다면 친구가 없어서 시간이 많다. 어쨋든 그는 크리스마스 트리를 장식하기 위하여 조금 특이한 전구를 만들어 그것들을 연결하여 트리를 장식하려는 계획을 세우고 있다.

 
류주가 만드는 전구는 다음과 같은 특징이 있다.
 
  • 전구는 항상 하나의 전원으로부터만 전력을 공급받을 수 있다.
  • 전구 자체가 다른 전구의 전원으로써 전력을 공급해주는 것이 가능하다.
  • 전원이 되는 전구는 자신에게 전원이 공급되면 자신에게 연결된 전구에게도 반드시 전원을 공급해주어야 한다.
 
여기까지만 했어도 좋을텐데 . . .
 
류주는 그래도 크리스마스까지 시간이 많이 남기 때문에 여기에 몇 가지를 손봐서 이러한 특징을 가지면서 약간 다른 2 종류의 전구를 만들었다.
 
  • type 1의 전구는 자신이 다른 전구의 전원이 될 때 연결된 전구 중에 하나의 전구에만 전원을 공급한다.
  • type 2의 전구는 자신이 다른 전구의 전원이 될 때 연결된 전구 모두에게 전원을 공급한다.
 
류주는 이러한 전구들을 연결하여 연결된 형태에 따라서 켜지는 전구의 형태가 다른 장식을 만들려고 한다. 그리고 그렇게 만든 전구 중에서 k번째 전구는 반드시 켜고 싶다. 하지만 전구가 동작하는 것이 생각보다 복잡하게 되자 류주는 전구들을 연결했을 때 어떻게 동작할지 예측하기가 힘들어졌다. (왜 복잡하게 만들었냐하면 그는 시간이 많다.) 어차피 방에서 혼자 보낼 크리스마스인데 무슨 고민을 하느냐고 생각할 수 있지만 가엾은 그를 위해서 전구가 어떻게 동작할지 출력해주는 프로그램을 작성해주자.
 
마지막으로 류주가 연결한 전구들의 특성은 다음과 같다.
 
  • 자기 자신으로 연결되는 전구는 없다.
  • 전원은 1번 전구에서부터 공급된다.
  • 모든 전구는 연결되어 있고 1번 전구로부터 임의의 전구까지 연결되어 있는 경로는 유일하다.
  • type 1의 전구에 전력이 공급될 때 연결된 전구들 중에 특별히 켜져야 될 전구가 없다면 연결된 전구 중에서 가장 낮은 번호의 전구에 전원을 공급한다.
  • 위의 특성들을 만족할 때 k번째 전구가 켜졌을 때 같이 켜지는 전구들은 유일하다.

입력 설명

첫 행에는 테스트 케이스의 수 T 가 주어진다. 각 테스트 케이스에 첫 줄에는 전구의 수 N 이 입력된다. (1 ≤ N ≤ 100) 그 다음 줄 부터 N 줄에 걸쳐서 i 번째 전구의 상태가 입력된다. (1 ≤ i ≤ N)

전구의 상태는 아래와 같은 형식으로 입력된다.
 
type m x1 x2 ... xm
 
여기서 type은 전구의 타입으로 1 또는 2가 입력된다.
m은 i번째 전구에 연결된 전구의 개수이다. (0 ≤ m ≤ N) x1x2..xm은 전구에 연결된 전구들의 번호이다. (1 ≤ xi ≤ N)
전구의 상태가 입력된 후 마지막 줄에 류주가 반드시 키고자 하는 전구의 번호 k가 입력된다. (1 ≤ k ≤ N)

출력 설명

각 테스트 케이스에 대해서 연결된 전구들 중에서 켜진 전구들의 번호를 한 줄에 오름차순으로 출력한다.

입력 예시 Copy

2
7
1 2 2 3
2 2 4 5
1 0
1 0
1 2 6 7
2 0
1 0
2
6
2 3 2 3 4
2 0
1 2 5 6
2 0
1 0
1 0
6

출력 예시 Copy

1 2 4 5 6 
1 2 3 4 6