Problem D
Bicikli
A bicycle race is being organized in a land far, far away.
There are
How many different ways can the route be set? Two routes are considered different if they do not use the exact same roads.
Input
The first line of input contains two integers
Each of the next
Towns may be connected by more than one road.
Output
Output the number of distinct routes that can be set on a single line. If that number has more than nine digits, output only the last nine digits of the number. If there are infinitely many routes, output “inf”.
Sample Input 1 | Sample Output 1 |
---|---|
6 7 1 3 1 4 3 2 4 2 5 6 6 5 3 4 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
6 8 1 3 1 4 3 2 4 2 5 6 6 5 3 4 4 3 |
inf |
Sample Input 3 | Sample Output 3 |
---|---|
31 60 1 3 1 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 26 27 27 28 27 28 28 29 28 29 29 30 29 30 30 31 30 31 31 2 31 2 |
073741824 |