CR07C3P5 - BICIKLI
A bicycle race is being organized in a land far, far away. There are N town in the land, numbered 1 through N. There are also M one-way roads between the towns. The race will start in town 1 and end in town 2. 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 N and M (1 ≤ N ≤ 10 000, 1 ≤ M ≤ 100 000), the number of towns and roads.
Each of the next M lines contains two different integers A and B, representing a road between towns A and B.
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".
Example
Input: 6 7 1 3 1 4 3 2 4 2 5 6 6 5 3 4 Output: 3
Input: 6 8 1 3 1 4 3 2 4 2 5 6 6 5 3 4 4 3 Output: inf
Input: 31 60 1 3 1 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 … … … 28 29 28 29 29 30 29 30 30 31 30 31 31 2 31 2 Output: 073741824
hide comments
Ognjen Arsenijevic:
2017-04-03 18:19:04
@Ahmed Salem [mrtempo] Are you sure that all test cases are correct, because when I submit this same problem on http://wcipeg.com/problem/coci063p5 it passes all test cases? Last edit: 2017-04-03 18:19:13 |
Added by: | Ahmed Salem [mrtempo] |
Date: | 2015-01-17 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 JS-MONKEY |
Resource: | COCI 2006/2007 #3 (http://hsin.hr/coci/archive/2006_2007/contest3_tasks.pdf) |