Outsourcing

Mr. Cooper manufactures science-fiction action figures and believes his local factory is too expensive. Having heard that workers abroad are far cheaper and more dedicated, he wants to move production to a low-wage country (to "outsource" it).

Before switching, he must be sure the new factory can build exactly the same kinds of action figures as the current one. Manufacturing is organized around assembly stations and transfer stations. An assembly station takes parts from a transfer station, performs a single operation on them, and delivers the result to a transfer station. Every factory has one starting transfer station that supplies raw parts and one final transfer station that collects finished figures.

A given kind of action figure requires a specific sequence of operations $s_1, s_2, \dots, s_\ell$. A factory can build that figure if there exist transfer stations $t_0, t_1, \dots, t_\ell$ such that $t_0$ is the starting station, $t_\ell$ is the final station, and for every $1 \le i \le \ell$ there is an assembly station that takes parts from $t_{i-1}$, performs operation $s_i$, and delivers to $t_i$.

Hence Mr. Cooper wants to know whether the local factory and the foreign factory can produce exactly the same sorts of action figures. He realizes that answering this may be an involved challenge, so he hires you to develop a computer solution. For each pair of factories, decide whether the local factory and the foreign factory can build exactly the same set of action figures.

The first line contains an integer $t$, the number of test cases ($0 < t \le 100$).

Each test case begins with a line of six integers $M_1\ N_1\ K_1\ M_2\ N_2\ K_2$: the local factory has $M_1$ assembly stations, $N_1$ transfer stations, and $K_1$ distinct operations, and the foreign factory has $M_2$ assembly stations, $N_2$ transfer stations, and $K_2$ distinct operations ($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$).

In each factory the transfer stations are numbered $0$ to $N-1$; station $0$ is the starting station and station $N-1$ is the final station. The next $M_1$ lines describe the local factory's assembly stations, one per line, as three integers $T_{in}\ T_{out}\ S$: the station takes parts from transfer station $T_{in}$, delivers the result to transfer station $T_{out}$, and performs operation $S$ ($0 \le S \le K_1 - 1$). For any single transfer station, no two of its outgoing assembly stations perform the same operation. The following $M_2$ lines describe the foreign factory's assembly stations in the same format.

For each test case print one line: eligible if the local and foreign factories can build exactly the same set of action figures, or not eligible otherwise.