아웃소싱

쿠퍼 씨는 공상과학 액션 피규어를 만드는 제조업자인데, 자국 공장의 비용이 너무 크다고 생각한다. 인건비가 훨씬 싸고 더 헌신적인 해외 노동자들이 있다는 이야기를 듣고, 그는 생산을 저임금 국가로 옮기는 아웃소싱을 고려하기로 했다.

공장을 옮기기 전에, 새 공장이 지금 공장과 정확히 같은 종류의 액션 피규어를 만들 수 있는지 반드시 확인해야 한다. 제조 공정은 조립소(assembly station) 와 이송소(transfer station) 로 구성된다. 하나의 조립소는 어떤 이송소에서 부품을 받아 한 가지 작업을 수행한 뒤, 그 결과를 어떤 이송소로 넘긴다. 모든 공장에는 원자재를 공급하는 시작 이송소가 하나, 완성된 피규어를 받는 최종 이송소가 하나 있다.

어떤 종류의 액션 피규어를 만들려면 정해진 작업 순서 $s_1, s_2, \dots, s_\ell$ 이 필요하다. 어떤 공장이 그 피규어를 만들 수 있다는 것은, 이송소들 $t_0, t_1, \dots, t_\ell$ 이 존재하여 $t_0$ 은 시작 이송소, $t_\ell$ 은 최종 이송소이고, 모든 $1 \le i \le \ell$ 에 대해 $t_{i-1}$ 에서 부품을 받아 작업 $s_i$ 를 수행하고 $t_i$ 로 넘기는 조립소가 존재한다는 뜻이다.

따라서 쿠퍼 씨는 자국 공장과 해외 공장이 정확히 같은 종류의 액션 피규어를 만들 수 있는지 알고 싶어 한다. 그는 이 질문에 답하는 것이 만만치 않은 일임을 알기에, 당신을 고용해 이를 위한 프로그램을 작성하게 한다. 각 공장 쌍에 대해, 자국 공장과 해외 공장이 정확히 같은 액션 피규어 집합을 만들 수 있는지 판정하라.

첫 줄에 테스트 케이스의 수 $t$ 가 주어진다 ($0 < t \le 100$).

각 테스트 케이스는 여섯 정수 $M_1\ N_1\ K_1\ M_2\ N_2\ K_2$ 로 시작한다. 자국 공장은 조립소 $M_1$ 개, 이송소 $N_1$ 개, 서로 다른 작업 $K_1$ 종류를 가지며, 해외 공장은 조립소 $M_2$ 개, 이송소 $N_2$ 개, 작업 $K_2$ 종류를 가진다 ($1 \le M_1, M_2 \le 10^5$; $1 \le N_1, N_2 \le 250$; $1 \le K_1, K_2 \le 250$).

각 공장에서 이송소는 $0$ 부터 $N-1$ 까지 번호가 매겨지며, $0$ 번이 시작 이송소, $N-1$ 번이 최종 이송소이다. 이어지는 $M_1$ 개의 줄은 자국 공장의 조립소를 하나씩 설명하며, 각 줄은 세 정수 $T_{in}\ T_{out}\ S$ 로 이루어진다. 이 조립소는 이송소 $T_{in}$ 에서 부품을 받아 작업 $S$ 를 수행한 뒤 결과를 이송소 $T_{out}$ 으로 넘긴다 ($0 \le S \le K_1 - 1$). 하나의 이송소에서 나가는 조립소들 중 같은 작업을 수행하는 것은 둘 이상 존재하지 않음이 보장된다. 그다음 $M_2$ 개의 줄은 같은 형식으로 해외 공장의 조립소를 설명한다.

각 테스트 케이스마다 한 줄을 출력한다. 자국 공장과 해외 공장이 정확히 같은 액션 피규어 집합을 만들 수 있으면 eligible 을, 그렇지 않으면 not eligible 을 출력한다.