# Painting vertices P76043

Statement html

You are given a directed graph, where some vertices are initially painted and some are not, and two vertices x and y. Please paint the minimum number of additional vertices so that there is a path from x to y that only passes through painted vertices.

Input

Input consists of several cases. Every case begins with the number of vertices n, the starting vertex x and the final vertex y. Next comes a number m, followed by m different arcs u v where uv. Follow a number p, followed by the p vertices initially painted. Assume 2 ≤ n ≤ 104, xy, 0 ≤ m ≤ 5n, and 0 ≤ pn. The vertices are numbered starting at 0.

Output

For every case, print the minimum number of vertices to paint so that there is a path from x to y that only passes through painted vertices, x and y included. If it is impossible, state so.

Public test cases
• Input

```2 1 0
1  1 0
0

2 0 1
0
2  0 1

5 0 2
6  0 1  1 2  0 3  3 1  3 4  4 2
4  0 3 4 2

8 7 0
11  4 1  6 0  7 4  5 3  7 5
1 6  6 7  0 2  5 1  4 2  3 6
3  6 4 2
```

Output

```2
impossible
0
3
```
• Information
Author