Bicikli
플래티넘 III의견: 0
A bicycle race is being organized in a land far, far away. There are \(N\) towns 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.
The first line of input contains two integers \(N\) and \(M\) (\(1 \le N, M \le 10000\)), 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 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.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 70점 |
6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 436 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3inf31 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 2073741824평가 및 의견
Bicikli
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Bicikli