Problem B: Turn Left

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

Input

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. name_i is the name of the i-th intersection. (x_i, y_i) 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. p_j and q_j 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:

• 2 ≤ m ≤ 1000, 0 ≤ x_i ≤ 10000, and 0 ≤ y_i ≤ 10000;
• 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.

Output

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.

Sample Input

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

Output for the Sample Input

2
impossible
13
4