Taro got a driverfs 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: gI 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?h

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 nname_{1}x_{1}y_{1}...name_{m}x_{m}y_{m}p_{1}q_{1}...p_{n}q_{n}src dst

*m* is the number of intersections. *n* is the number of roads. *name _{i}* is the name of the

You may assume all of the followings:

- 2 ≤
*m*≤ 1000, 0 ≤*x*≤ 10000, and 0 ≤_{i}*y*≤ 10000;_{i} - each intersection name is a sequence of one or more alphabetical characters at most 25 character long;
- no intersections share the same coordinates;
- no pair of roads have common points other than their endpoints;
- no road has intersections in the middle;
- no pair of intersections has more than one road;
- Taro can start the car in any direction; and
- the source and destination intersections are different.

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 gpassedh (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 gimpossibleh 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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2007
, Day 2, Tokyo, Japan, 2007-09-23

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/