기어박스

제이크는 '공부 삼아' 자동차의 기어박스를 분해했다가 다시 조립하기로 했다. 기어박스는 여러 개의 기어(gear), 코그(cog), 스프로킷(sprocket)과 몇 개의 스프링·피니언이 들어 있는 상자다. 이 부품들은 복잡하게 맞물려 있어서, 모든 부품이 원래 자리에 제대로 돌아갔는지 제이크는 확신하지 못한다.

모든 기어는 금속 축(rod) 위에 끼워져 있다. 한 축 위의 기어 하나가 돌면 그 축 위의 모든 기어가 같은 각도만큼 함께 돈다. 축끼리는 스프링과 플라스틱 막대로 연결되어 있는데, 이 부분은 제대로 맞추었다고 제이크는 확신한다. 반면 코그와 스프로킷은 어디에도 연결되어 있지 않고 상자 안에서 자유롭게 덜그럭거린다.

문제는 일부 기어가 서로 맞물려(interlock) 있어서 주 구동축이 멈춰 버릴(jam) 수 있다는 점이다. 이 기어들은 최신 InfiniTeeth 기술로 만들어져 이빨(teeth) 수를 셀 수 없다. 대신 모든 기어에는 '종류 번호(type number)'가 있으며, 같은 종류의 기어는 이빨 수가 같다. 설명서에 따르면, 각 종류의 기어가 이빨을 몇 개 갖든 상관없이 모든 축이 돌 수 있어야 한다. 따라서 제이크는 자신의 기어박스가 이 조건을 만족하면 확실히 올바르게 조립된 것이라고 결론짓는다.

두 기어가 맞물리면 두 축은 서로 반대 방향으로 돌고, 각속도는 이빨 수에 반비례한다. 예를 들어 두 축에 세 개의 기어가 있고 위쪽 두 기어가 맞물려 있다면 두 축은 반대 방향으로 돌며, 한 기어의 이빨이 36개이고 맞물린 기어의 이빨이 24개라면 24개짜리 기어가 달린 축이 1.5배 빠르게 돈다.

첫 줄에는 양의 정수 하나, 즉 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

• 세 정수 $n_g$, $n_r$, $n_i$ (모두 $< 10^5$): 각각 기어, 축, 맞물림의 개수.
• $n_g$개의 줄: 각 줄에 정수 $t_i$와 $r_i$ ($0 < t_i < 100$, $0 \le r_i < n_r$) — 기어 $i$의 종류 번호와 그 기어가 놓인 축의 번호.
• $n_i$개의 줄: 각 줄에 정수 $a_j$와 $b_j$ ($0 \le a_j < b_j < n_g$) — 기어 $a_j$와 $b_j$가 서로 맞물려 있음을 나타낸다.

각 테스트 케이스마다 한 줄을 출력한다. 기어박스가 확실히 올바르게 조립되었으면 ok를, 그렇지 않으면 jammed를 출력한다.