3956번 - 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₁, s₂, s₃, ... , s_ℓ of assembly operations. A factory can produce these action figures if there are transfer stations t₀, t₁, ··· , t_ℓ such that t0 is the starting station, tℓ is the final station, and for all 1 ≤ i ≤ ℓ 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 starts with a line containing one integer t, the number of test cases (0 < t ≤ 100). Each test case starts with a line of six integers M₁, N₁, K₁, M₂, N₂, and K₂, where the local factory has M₁ assembly stations, N₁ transfer stations and K₁ different assembly operations (1 ≤ M₁ ≤ 10⁵; 1 ≤ N₁ ≤ 250; 1 ≤ K₁ ≤ 250). The transfer stations are numbered from 0 to N₁ − 1 and 0 denotes the starting station and N₁ − 1 the final station. Then input is followed by M₁ 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. 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₂, N₂ and K₂ and consequently the next M₂ lines of input describe the assembly stations of the foreign factory.

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”.