Problem: John is playing a famous console game named 'Tales of Algorithmers.' Now he is facing the last dungeon called 'Blue Forest.' To find out the fastest path to run through the very complicated dungeon, he tried to draw up the dungeon map.

The dungeon consists of several floors. Each floor can be described as a connected simple plane graph. Vertices of the graph are identified by X-Y coordinate, and the length of an edge is calculated by Euclidean distance. A vertex may be equipped with a one-way warp gate. If John chooses to use the gate, it brings John to another vertex in a possibly different floor. The distance between a warp gate and its destination is considered as 0.

One vertex has at most one warp gate, though some vertices might be the destination of multiple warp gates.

He believed he made one map for each floor, however after drawing maps of all the floors, he noticed that he might have made a few mistakes. He might have drawn the same floor several times, and might have forgotten to mark some warp gates in the maps. However, he was sure he marked all warp gates at least once. So if the maps of same floor are unified to one map, all the warp gates must be described there. Luckily there are no floors which have the same shape as the other floors, so if two (or more) maps can be unified, they must be the maps of the same floor. Also, there is no floor which is circular symmetric (e.g. a regular triangle and a square).

Map A and map B can be unified if map B can be transformed to map A using only rotation and parallel translation. Since some of the warp gates on maps might be missing, you should not consider the existence of warp gates when checking unification. If it is possible to unify map A and map B, a vertex on map A and the corresponding vertex on map B are considered as 'identical' vertices. In other words, you should treat warp gates on map B as those on map A where the warp gates are located on the corresponding vertices on map A. Destinations of warp gates should be treated similarly. After that you can forget map B. It is guaranteed that if both map A and map B have warp gates which are on the identical vertices, the destinations of them are also identical.

Remember, your task is to find the shortest path from the entrance to the exit of the dungeon, using the unified maps.



Input

The input consists of multiple datasets. Each dataset is in the following format.

n
component1 component2 ...
componentn sl sn
dl dn


n is a positive integer indicating the number of maps. componenti describes the i-th map in the following format.

A
x1 y1
x2 y2
...
xA yA
B
s1 d1
s2 d2
...
sB dB
C sn1 dl1 dn1
sn2 dl2 dn2
...
snC dlC dnC


A denotes the number of vertices in the map. Each of the following A lines contains two integers xi and yi representing the coordinates of the i-th vertex in the 2-dimensional plane. B denotes the number of the edges connecting the vertices in the map. Each of the following B lines contains two integers representing the start and the end vertex of each edge. Vertices on the same map are numbered from 1.

C denotes the number of warp gates. Each of the following C lines has three integers describing a warp gate. The first integer is the vertex where the warp gate is located. The second and the third integer are the indices of the map and the vertex representing the destination of the warp gate, respectively. Similarly to vertices, maps are also numbered from 1.

After the description of all maps, two lines follow. The rst line contains two integers sl and dl , meaning that the entrance of the dungeon is located in the sl-th map, at the vertex dl. The last line has two integers sn and dn, similarly describing the location of the exit.

The values in each dataset satisfy the following conditions:

* 1 ≤ n ≤ 50,
* 3 ≤ A ≤ 20,
* A - 1 ≤ B ≤ A(A - 1)/2,
* 0 ≤ C ≤ A, and
* -10,000 ≤ xi, yi ≤ 10,000.

Output

For each dataset, print the distance of the shortest path from the entrance to the exit. The output should not contain an absolute error greater than 10-1. If there is no route, print -1.

Example

Input

2
5
0 0
10 0
20 0
30 0
30 10
4
1 2
2 3
3 4
4 5
2
1 2 4
3 2 2
5
-10 0
0 0
0 -10
0 -20
0 -30
4
1 2
2 3
3 4
4 5
1
4 1 3
1 1
2 1
4
3
4 3
0 0
5 0
2
1 2
2 3
0
3
0 0
3 4
0 5
2
1 2
1 3
1
2 3 4
4
0 13
0 0
13 0
13 13
4
1 2
1 4
2 3
2 4
0
4
5 12
0 0
-7 17
-12 5
4
1 2
2 3
2 4
4 3
0
1 1
4 1
4
3
0 0
2 0
0 4
2
1 2
1 3
0
3
0 0
-2 0
0 4
2
1 2
1 3
1
1 4 1
3
0 0
1 0
0 2
2
1 2
1 3
1
1 4 1
3
0 0
2 0
0 4
2
1 2
2 3
0
1 1
4 1
0


Output

10.0000000000
41.3847763109
-1.000000000

Solution (in CPP):

Solution:
#include<cmath>
#include<queue>
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef pair<int,int> pii;

const double INF=1e77,EPS=1e-9;

struct Point{
	int x,y;
	Point operator-(const Point &p)const{ return (Point){x-p.x,y-p.y}; }
};

struct Edge{
	int j,v;
	double cost;
	bool warp;
};

struct Floor{
	int n;
	vector<Edge> adj[20];
};

int  dot (const Point &p,const Point &q){ return p.x*q.x+p.y*q.y; }
int cross(const Point &p,const Point &q){ return p.x*q.y-p.y*q.x; }

double norm2(const Point &p){ return dot(p,p); }

double dist(const Point &p,const Point &q){ return sqrt(norm2(p-q)); }

bool identify(int i,int j,const Floor *F,const Point P[50][20],int *sigma){
	if(F[i].n!=F[j].n) return false;

	int n=F[i].n;
	rep(a,n) rep(b,n) if(a!=b) {
		bool ok=true;
		rep(u,n){
			int v;
			for(v=0;v<n;v++){
				Point vec_i[2]={P[i][0]-P[i][u],P[i][1]-P[i][u]};
				Point vec_j[2]={P[j][a]-P[j][v],P[j][b]-P[j][v]};
				if(norm2(vec_i[0])==norm2(vec_j[0])
				&& norm2(vec_i[1])==norm2(vec_j[1])
				&&  dot (vec_i[0],vec_i[1])== dot (vec_j[0],vec_j[1])
				&& cross(vec_i[0],vec_i[1])==cross(vec_j[0],vec_j[1]))
					break;
			}
			if(v<n) sigma[u]=v;
			else    ok=false;
		}
		if(!ok) continue;

		bool adj_i[20][20]={},adj_j[20][20]={};
		rep(u,n) rep(k,F[i].adj[u].size()) {
			Edge e=F[i].adj[u][k];
			if(!e.warp) adj_i[u][e.v]=true;
		}
		rep(u,n) rep(k,F[j].adj[u].size()) {
			Edge e=F[j].adj[u][k];
			if(!e.warp) adj_j[u][e.v]=true;
		}

		rep(u,n) rep(v,n) if(adj_i[u][v]!=adj_j[sigma[u]][sigma[v]]) ok=false;
		if(!ok) continue;

		return true;
	}

	return false;
}

int main(){
	for(int n;scanf("%d",&n),n;){
		Floor F[50];
		Point P[50][20];
		rep(i,n){
			scanf("%d",&F[i].n);
			rep(k,F[i].n) scanf("%d%d",&P[i][k].x,&P[i][k].y);
			int b; scanf("%d",&b);
			rep(k,b){
				int u,v; scanf("%d%d",&u,&v); u--; v--;
				F[i].adj[u].push_back((Edge){i,v,dist(P[i][u],P[i][v])});
				F[i].adj[v].push_back((Edge){i,u,dist(P[i][u],P[i][v])});
			}
			int c; scanf("%d",&c);
			rep(k,c){
				int u,j,v; scanf("%d%d%d",&u,&j,&v); u--; j--; v--;
				F[i].adj[u].push_back((Edge){j,v,0,true});
			}
		}
		int si,su,gi,gu; scanf("%d%d%d%d",&si,&su,&gi,&gu); si--; su--; gi--; gu--;

		rep(j,n) rep(i,j) {
			int sigma[20];
			if(identify(i,j,F,P,sigma)){
				rep(u,F[i].n){
					int v=sigma[u];
					F[i].adj[u].push_back((Edge){j,v,0,true});
					F[j].adj[v].push_back((Edge){i,u,0,true});
				}
			}
		}

		double d[50][20],ans=-1;
		rep(i,n) rep(u,20) d[i][u]=INF;
		d[si][su]=0;

		priority_queue< pair<double,pii> > pq;
		pq.push(make_pair(0,make_pair(si,su)));
		while(!pq.empty()){
			pair<double,pii> a=pq.top(); pq.pop();
			int i=a.second.first,u=a.second.second;
			if(d[i][u]+EPS<-a.first) continue;

			if(i==gi && u==gu){ ans=d[gi][gu]; break; }

			rep(k,F[i].adj[u].size()){
				Edge e=F[i].adj[u][k];
				double nextd=d[i][u]+e.cost;
				if(nextd+EPS<d[e.j][e.v]){
					d[e.j][e.v]=nextd;
					pq.push(make_pair(-nextd,make_pair(e.j,e.v)));
				}
			}
		}

		printf("%f\n",ans);
	}

	return 0;
}