Hide

Problem D
Outsourcing

Mr. Cooper is a manufacturer of science fiction action figures and he thinks that his local factory causes too many costs. He once heard of certain foreign countries where workers are much less expensive and also more dedicated. So he decided to look for an available action figure factory in some low-wage country to follow the current trend of Outsourcing.

It is of course indispensable for him to know if the new factory is capable of producing exactly the same sorts of action figures as the current one. The manufacturing process is organised in terms of assembly stations and transfer stations. An assembly station receives parts from a transfer station, performs a specific operation on the parts and delivers it to a transfer station. The factories have one starting transfer station delivering raw parts and one final transfer station receiving the completed action figures.

One sort of action figures needs a precise sequence $s_1, s_2, s_3, \ldots , s_\ell $ of assembly operations. A factory can produce these action figures if there are transfer stations $t_0, t_1, \cdots , t_\ell $ such that $t_0$ is the starting station, $t_\ell $ is the final station, and for all $1 \le i \le \ell $ there is an assembly station that receives from $t_{i-1}$, delivers to $t_ i$, and performs operation $s_ i$.

Hence, Mr. Cooper wants to know if the local factory and the foreign factory can produce exactly the same sorts of action figures. He recognizes that answering this question may be an involved challenge. So, he decides to spend an amount of his yet to save money on you, to make you develop a computer solution for his problem.

Input

Input starts with a line containing one integer $t$, the number of test cases ($0 < t \le 100$). Each test case starts with a line of six integers $M_1, N_1, K_1, M_2, N_2,$ and $K_2$, where the local factory has $M_1$ assembly stations, $N_1$ transfer stations and $K_1$ different assembly operations ($1 \le M_1 \le 10^5; 1 \le N_1 \le 250; 1 \le K_1 \le 250$). The transfer stations are numbered from $0$ to $N_1-1$ and $0$ denotes the starting station and $N_1-1$ the final station. Then input is followed by $M_1$ lines specifying the assembly stations of the local factory. Every line contains three integers, $T_{in}, T_{out}, S$, where $T_{in}$ is the transfer station delivering to the assembly station, $T_{out}$ is the transfer station receiving the assembly results and $S$ gives the performed operation by a number between $0$ and $K_1-1$. For every transfer station it is guaranteed that there are not two receiving assembly stations performing the same operation. The foreign factory is described analogously by $M_2, N_2$ and $K_2$ and consequently the next $M_2$ lines of input describe the assembly stations of the foreign factory.

Output

For every test case print a line containing “eligible” if the local and the foreign factory are capable of manufacturing exactly the same action figures and otherwise print “not eligible”.

Sample Input 1 Sample Output 1
2
3 4 2 3 4 3
0 2 1
1 3 0
2 3 0
0 2 1
2 1 2
2 3 0
3 3 2 2 2 2
0 1 0
1 1 0
1 2 1
0 0 0
0 1 1
eligible
not eligible

Please log in to submit a solution to this problem

Log in