COCI 2006/2007, Contest #3

Task 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".

Sample Tests

6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4

3

6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3

inf

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

073741824

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Feb 13, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

My code got accepted here but got Wrong Answer on [url=http://www.spoj.com/problems/CR07C3P5/]SPOJ[/url]. Here's a case where it went wrong:

[code]
6 7     
3 1
1 3
1 4
4 5
3 6
6 2
5 3
[/code]

Correct answer is "inf". (I don't want to spoil the problem for others so I won't describe what is special about this type of cases)

 
6 7      
3 1 
1 3 
1 4 
4 5 
3 6 
6 2 
5 3 

Do not post test cases and answers into the comments. If you are referring to a certain test case then use the test case number

He's not posting a PEG case, it's from SPOJ. Actually, this is pretty useful to check that your solution really is correct if you pass PEG tests, but a case like that isn't tested.