|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|8 초 (추가 시간 없음)||512 MB||0||0||0||0.000%|
Taro got a driver’s license with a great effort in his campus days, but unfortunately there had been no opportunities for him to drive. He ended up obtaining a gold license.
One day, he and his friends made a plan to go on a trip to Kyoto with you. At the end of their meeting, they agreed to go around by car, but there was a big problem; none of his friends was able to drive a car. Thus he had no choice but to become the driver.
The day of our departure has come. He is going to drive but would never turn to the right for fear of crossing an opposite lane (note that cars keep left in Japan). Furthermore, he cannot U-turn for the lack of his technique. The car is equipped with a car navigation system, but the system cannot search for a route without right turns. So he asked to you: “I hate right turns, so, could you write a program to find the shortest left-turn-only route to the destination, using the road map taken from this navigation system?”
The input consists of multiple data sets. The first line of the input contains the number of data sets. Each data set is described in the format below:
m n name1 x1 y1 ... namem xm ym p1 q1 ... pn qn src dst
m is the number of intersections. n is the number of roads. namei is the name of the i-th intersection. (xi, yi) are the integer coordinates of the i-th intersection, where the positive x goes to the east, and the positive y goes to the north. pj and qj are the intersection names that represent the endpoints of the j-th road. All roads are bidirectional and either vertical or horizontal. src and dst are the names of the source and destination intersections, respectively.
You may assume all of the followings:
Note that there may be a case that an intersection is connected to less than three roads in the input data; the rode map may not include smaller roads which are not appropriate for the non-local people. In such a case, you still have to consider them as intersections when you go them through.
For each data set, print how many times at least Taro needs to pass intersections when he drive the route of the shortest distance without right turns. The source and destination intersections must be considered as “passed” (thus should be counted) when Taro starts from the source or arrives at the destination. Also note that there may be more than one shortest route possible.
Print “impossible” if there is no route to the destination without right turns.
2 1 KarasumaKitaoji 0 6150 KarasumaNanajo 0 0 KarasumaNanajo KarasumaKitaoji KarasumaKitaoji KarasumaNanajo 3 2 KujoOmiya 0 0 KujoAburanokoji 400 0 OmiyaNanajo 0 1150 KujoOmiya KujoAburanokoji KujoOmiya OmiyaNanajo KujoAburanokoji OmiyaNanajo 10 12 KarasumaGojo 745 0 HorikawaShijo 0 870 ShijoKarasuma 745 870 ShijoKawaramachi 1645 870 HorikawaOike 0 1700 KarasumaOike 745 1700 KawaramachiOike 1645 1700 KawabataOike 1945 1700 KarasumaMarutamachi 745 2445 KawaramachiMarutamachi 1645 2445 KarasumaGojo ShijoKarasuma HorikawaShijo ShijoKarasuma ShijoKarasuma ShijoKawaramachi HorikawaShijo HorikawaOike ShijoKarasuma KarasumaOike ShijoKawaramachi KawaramachiOike HorikawaOike KarasumaOike KarasumaOike KawaramachiOike KawaramachiOike KawabataOike KarasumaOike KarasumaMarutamachi KawaramachiOike KawaramachiMarutamachi KarasumaMarutamachi KawaramachiMarutamachi KarasumaGojo KawabataOike 8 9 NishikojiNanajo 0 0 NishiojiNanajo 750 0 NishikojiGojo 0 800 NishiojiGojo 750 800 HorikawaGojo 2550 800 NishiojiShijo 750 1700 Enmachi 750 3250 HorikawaMarutamachi 2550 3250 NishikojiNanajo NishiojiNanajo NishikojiNanajo NishikojiGojo NishiojiNanajo NishiojiGojo NishikojiGojo NishiojiGojo NishiojiGojo HorikawaGojo NishiojiGojo NishiojiShijo HorikawaGojo HorikawaMarutamachi NishiojiShijo Enmachi Enmachi HorikawaMarutamachi HorikawaGojo NishiojiShijo 0 0
2 impossible 13 4