E. Escape from Markov
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Examples
Input
4 4 1 4
1 2
2 3
3 4
4 1
2 1 4 3
1 3
Output
2
Input
4 4 1 4
1 2
2 3
3 4
4 1
2 1 4 3
1 2
Output
2
Input
6 5 1 4
1 2
2 3
3 4
4 5
5 6
5 6 5 4
1 6
Output
7
Input
2 1 1 2
1 2
2 1
1 2
Output
IMPOSSIBLE