Description

There are some theories that if one keeps doing something, the result which that something may lead to will eventually take place. For example, if one crosses a road every day, he will certainly be run over by a car. Jon is a man who believe in such theories. Unfortunately, he lost Cely. But he knows that if he keeps waiting in some place on the earth, they will meet again at last.

There are a number of places on the earth. Some are connected by bidirectional roads. (To make things easier, we assume that each road takes exactly 5 days to travel.) Jon’s home in the place numbered zero. For the reason of fate, he will never know where Cely lives. But during the first days, he will go to some places in search of Cely. Each time he goes to a place, he takes the shortest possible path. When he reaches the place without finding Cely, he will immediately take the same way back to his home. A long wait will follow his last trip back home.

Cely will appear in some places on some days. If Jon reaches those places as his destination on the very day when Cely appears there, they are lucky to meet. Otherwise they will regrettably miss each other, even if they are in the same place on the way.

Jon will do nothing but search blindly and wait reverently. When will they meet?

Input

The input contains four parts separated by a blank line:

Part 1: An integer M (2 ≤ M < 10,000) which is the number of places. The places are number 0 through M − 1.

Part 2: An integer R (0 ≤ R < 1,000) which is the number of roads and is followed by R lines each giving the numbers of two places connected by a road.

Part 3: An integer F (0 ≤ F < M) which is the number of Jon’s destinations and is followed by a line containing the numbers of the destinations in the order Jon reaches them.

Part 4: An integer T (0 ≤ T < M) which is the number of Cely’s appearances and is followed by T lines each giving a pair of integers p and d meaning Cely will appear in the place numbered p on day d in increasing order of d.

Output

Output the earliest day when Jon and Cely will meet. If they will never meet or Jon cannot reach any of his destinations before meeting Cely, output “Being expected..”.

4

2
0 1
1 2

2
1 2

3
2 5 
1 150 
0 3652

3652

Hint

Jon’s whole trip of search described in the sample input will be: home (day 0) → place 1 (day 5) → home (day 10) → place 2 (day 20) → home (day 30). On none of these five days can Jon meet Cely. But Jon’s patient wait is rewarded on day 3,652, when Cely arrives at his home.

Source

POJ Monthly--2006.05.28, Judas