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 *u* ≠ *v*.
Follow a number *p*,
followed by the *p* vertices initially painted.
Assume 2 ≤ *n* ≤ 10^{4}, *x* ≠ *y*, 0 ≤ *m* ≤ 5*n*,
and 0 ≤ *p* ≤ *n*.
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
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Desè Concurs de Programació de la UPC - Semifinal
- Date
- 2012-06-30