Little Vitta needs to go from home to school every day. On her way to school, there are n crossing and m roads in total. Because of lazy, she often gets up late in the morning. In order to get to school on time, she wishes that she can always go to school in the shortest path.(Assume that the time cost on every road is 1. And all roads are bidirectional. That is to say, if she can go from A to B, she always can go from B to A). But on some specific crossings, there are some terrible insects which makes Vitta scared. She expects the crossings which has insects don't exceed k. She wants know the number of all possible paths, can you help her?
Input
We assume Vitta's home is node 1, and the school is node n.
For each case, there are 3 integers in first line, m n k(m <= 1000000, n <= 5000, k <= 50), as the problem statement says.
In the following n lines, every line contains 2 integer x and y. y equals 1 means node x has terrible insects else if y equals 0 means there is no insect.
In the following m lines, every line contains 2 integer p and q, which means node p and node q is linked.
Output
For each case, output contains only 1 line.
If the path satisfies the requirement exists, you only need to output the numbers of paths. If not, you should output "Impossible!"
Sample Input
11 8 1
1 0
2 1
3 0
4 0
5 1
6 1
7 0
8 0
1 2
1 3
1 4
2 5
2 6
3 5
3 7
4 6
5 8
6 8
7 8
Sample Output
3
Hint To Sample
3 possible paths are 1-3-5-8 1-4-6-8 1-3-7-8
