### 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

## Input6 7 1 3 1 4 3 2 4 2 5 6 6 5 3 4 ## Output3 |
## Input6 8 1 3 1 4 3 2 4 2 5 6 6 5 3 4 4 3 ## Outputinf |
## Input31 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 ## Output073741824 |

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)

nibnalinon Jan 06, 2017 - 3:27:25 pm UTC Weak test data?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)

GirishRengaduraion Jan 06, 2017 - 4:45:15 pm UTC Re: Weak test data?spencereiron Jan 06, 2017 - 5:16:30 pm UTC Re: Weak test data?