## COCI '06 Contest 3 #5 Bicikli

View as PDF

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem types

A bicycle race is being organized in a land far, far away. There are towns in the land, numbered through . There are also one-way roads between the towns. The race will start in town and end in town .

How many different ways can the route be set? Two routes are considered different if they do not use the exact same roads.

#### Input Specification

The first line of input contains two integers and , the number of towns and roads.

Each of the next lines contains two different integers and , representing a road between towns and .

Towns may be connected by more than one road.

#### Output Specification

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

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

#### Sample Output 1

3

#### Sample Input 2

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

#### Sample Output 2

inf

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

#### Sample Output 3

073741824

Note that you have to print leading zeros for big numbers, otherwise it'll be marked WA.