COCI '06 Contest 3 #5 Bicikli

View as PDF

Submit solution


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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 Specification

The first line of input contains two integers N and M (1 \le N \le 10\,000, 1 \le M \le 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 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

Comments


  • 0
    discoverMe  commented on May 8, 2019, 9:32 a.m. edit 2

    wait nvm


  • 8
    kobortor  commented on April 9, 2017, 11:59 p.m.

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


  • -6
    jimgao  commented on Feb. 2, 2017, 1:03 p.m. edit 2

    This comment is hidden due to too much negative feedback. Click here to view it.