아이디어

아이디어의 독특한 점은 사용해도 소모되지 않는다는 것입니다. 좋은 아이디어는 그 가치를 잃지 않으면서 임의로 많은 사람에게 도움이 될 수 있고, 더 나은 아이디어를 이끌어내는 바탕이 되기도 합니다. 각 사람은 특정한 아이디어 집합을 바탕으로 새로운 아이디어를 만듭니다.

아이디어를 주고받기 위해 사람들은 한 방향으로만 흐르는 관(tube)들로 이루어진 전 세계적 통신망으로 연결되어 있습니다. 패킷(packet)이라는 호기심 많은 생물들이 관을 따라 이동하며 아이디어를 한 사람에게서 다른 사람에게로 나릅니다. 관은 단방향이므로 각 사람은 들어오는 관과 나가는 관을 각각 0개 이상 가질 수 있습니다. 모든 패킷은 $0$번 사람에서 출발하여 다음 알고리즘을 반복합니다.

1. 현재 사람이 만든 모든 아이디어를 배우고 기억합니다.
2. 현재 사람에게 나가는 관이 없으면 멈춥니다.
3. 그렇지 않으면 나가는 관 중 하나를 임의로 골라 그 관을 통해 새로운 사람에게 이동합니다.
4. 그 새로운 사람에게, 그가 다른 사람들로부터 필요로 하는 모든 아이디어를 알려 줍니다.
5. 1번으로 돌아갑니다.

각 사람은 특정한 아이디어 집합을 필요로 하며(도착 시 반드시 전달받아야 함), 특정한 아이디어 집합을 만듭니다(방문하는 모든 패킷에게 가르쳐 줌). 한 사람에 대해 같은 아이디어가 필요 목록과 생성 목록에 동시에 나타나는 일은 없지만, 서로 다른 여러 사람이 같은 아이디어를 각자 독립적으로 만들 수는 있습니다.

입력은 다음을 보장합니다. 패킷은 $0$번 사람에서 모든 사람에게 도달할 수 있으며, 어떤 사람 $P$가 어떤 아이디어를 필요로 할 때 패킷이 $P$에 이르는 모든 경로는 이미 그 아이디어를 만드는 누군가를 지나온 상태입니다.

패킷의 부담을 줄이기 위해, 패킷이 특정 관을 지나는 동안 일부 아이디어를 잊게 하여 임의의 순간에 기억하는 아이디어 수를 최소화하려고 합니다. 단, 패킷이 어떤 경로를 택하든 사람에게 도착할 때마다 그 사람이 필요로 하는 모든 아이디어를 이미 알고 있어야 한다는 조건은 반드시 지켜야 합니다. 각 관에 대해, 패킷이 그 관을 지나는 동안 반드시 기억하고 있어야 하는 아이디어의 최소 집합을 구하세요. 이 최소 집합은 유일하게 결정됩니다.

첫째 줄에는 테스트 케이스의 수가 주어집니다. 각 테스트 케이스는 세 정수 $N$, $M$, $I$가 주어지는 줄로 시작하며, 이는 각각 사람 수, 관의 수, 아이디어 수이고 모두 $1$ 이상 $1000$ 이하입니다. 사람은 $0$부터 $N-1$까지, 아이디어는 $0$부터 $I-1$까지 번호가 매겨지며, 모든 패킷은 $0$번 사람에서 출발합니다.

이어서 $2N$개의 줄이 $0$번부터 $N-1$번 사람 순서로 사람마다 두 줄씩 주어집니다. 사람 $p$의 두 줄 중 첫째 줄에는 $p$가 필요로 하는 아이디어들이, 둘째 줄에는 $p$가 만드는 아이디어들이 공백으로 구분된 정수로 주어지며, 두 줄 중 어느 쪽이든 비어 있을 수 있습니다. 같은 사람의 두 줄에 같은 아이디어가 동시에 나타나지는 않습니다.

마지막으로 $M$개의 줄이 주어지며, 각 줄에는 한 관의 출발 사람과 도착 사람을 나타내는 두 정수가 주어집니다.

각 테스트 케이스에 대해, 입력과 같은 순서로 관마다 한 줄씩 총 $M$개의 줄을 출력합니다. 각 줄에는 패킷이 그 관을 지나는 동안 반드시 지녀야 하는 최소 아이디어 집합의 원소들을 증가하는 순서로 출력합니다. 그 집합이 비어 있으면 빈 줄을 출력합니다.