문제
배관공 서준이는 여러 파이프들을 가지고 있다. 서준이는 파이프들을 잇는 작업을 진행하려고 한다.
그러나 여러 파이프들을 이을 경우 흐름이 어떻게 이루어지는지 파악하기 힘들어서 작업에 어려움을 겪고 있다.
파이프는 역류방지 시스템을 갖추고 있어, 방향을 맞춰서 이어야 한다.
파이프는 파이프 조각들로 이루어져 있으며
각 파이프 조각은 숫자가 매겨져 있다.
예를 들어 파이프 A가 시작 1, 끝 5인 (1,2,3,4,5) 로 이루어져 있고,
파이프 B가 시작 9, 끝 5인 (9,8,7,6,5)로 이루어져 있을 때,
파이프 B를 파이프 A의 3번 파이프 조각에 연결하면
모양이 되고,
파이프 B의 8에 물을 공급하게 되면 8 7 6 5 3 4 5 순서로 흐르게 된다.
파이프 A의 2에 물을 공급하게 되면 2 3 4 5 순서로 흐르게 된다.
파이프 종류와
각 파이프의 조각 번호, 파이프간 연결 관계가 주어졌을때,
물이 공급되는 위치가 주어지면, 물이 흐르는 순서대로 파이프 조각 번호를 출력하는 프로그램을 작성하자.
공급한 물이 순환할 경우 Impossible을 출력한다.
입력
파이프의 수 N이 첫번째 줄에 주어진다.
그 다음 N줄에 걸쳐 입력이 주어지는데, 각 줄의 첫번째 숫자는 i번 파이프의 조각 수 ni, 그 이후로 시작 조각부터 ni 개의 조각 번호가 공백을 구분으로 한 줄로 주어진다.
다음 줄에는 연결 관계의 수 M이 주어진다.
그 다음 M줄에 걸쳐 세개의 숫자, A, B, Bn이공백을 구분으로 주어지는데, 이 의미는 A번 파이프 의 끝이 B번 파이프의 Bn번째에 잇는다는 의미이다.
다음 줄에는 질문의 수 Q가 주어진다.
그 다음 Q줄에 걸쳐 두개의 숫자, A, An이 공백을 구분으로 주어지는데, 이 의미는 A번 파이프의 An번째에 물을 공급할 경우, 물이 흐르는 순서대로 파이프 조각 번호를 출력하라는 의미이다.
0 < N, M, Q, n, A, B, An, Bn <= 10)
물이 양방향으로 갈라지는 상황은 주어지지 않는다.
출력
Q줄에 걸쳐 각 줄에 파이프 번호 경로를 한 줄로 공백을 구분으로 출력한다. 물이 순환하는 경우 Impossible을 출력한다.
예제1
2
512345
598765
1
213
2
22
12
8765345
2345