Come Minion!
Time limit1sMemory limit1024 MB
For each map, decide whether location 0 can reach location n-1 using only routes whose trial is not on the ninja's banned list.
Problem
Welcome, treasure hunter! I am the great and powerful interplanetary ninja, and you are my minion. We must hurry to save this planet from the evil "Dialog Not Found". We must travel across the land so that I may stop "Dialog Not Found" from carrying out its evil plans. Also, minion, I cannot overcome a great many trials. Some of them are being looked at, handshakes, and even stairs.
Given a map of locations, the routes between them, and the trials on those routes, help the ninja reach the target. The ninja must avoid every trial it cannot overcome. Then tell the ninja whether it can reach the target and save the world.
Input
The first line contains a positive integer m, the number of maps to check. Each map starts with an integer t (0 <= t <= 50), the number of trials the ninja cannot overcome. The next t lines list these trials, one per line. The following line contains two integers n (2 <= n <= 30) and e (0 <= e <= 500), where n is the number of locations (numbered 0 through n-1) and e is the number of routes. The ninja starts at location 0 and its target is location n-1.
Each of the next e lines contains two integers La and Lb and a string Q, the trial on that route. The ninja can travel between La and Lb in either direction as long as the route's trial Q is not on the list of trials it cannot overcome. There is at most one route between any two locations, and each route has exactly one trial. Trial names use only lowercase letters and are 1 to 20 characters long. Any trial not on the ninja's list can be overcome. Values on a line are separated by exactly one space, with no leading or trailing spaces.
Output
For each map, print a single line containing 1 if the ninja can reach the target, or 0 if it cannot.