Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2923
Calculate Roads

Time Limit: 5 Seconds      Memory Limit: 32768 KB

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?


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.


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


Hint To Sample

3 possible paths are 1-3-5-8 1-4-6-8 1-3-7-8

Tester: YANG, Kete

Author: WANG, Naiyan
Source: ZOJ Monthly, February 2008
Submit    Status