How many roads lead to Rome?
Statement
Goal
Someone just told you all roads lead to Rome.As a matter of fact, this is not true.
In order to restore scientific truth, you must write a program that counts the actual number of paths from Paris to Rome, where cities are visited at most once.
To start with, you are given a collection of all paths that directly connect two individual cities and where each city is defined by a number from 1 to 100. Paris has label 1, and Rome has label 100.
One may use paths both ways.
Let us illustrate the problem with a simple example:
you are given 5 paths:
1 50
50 100
25 50
75 25
100 75
So, we have 5 cities:
- 1 (Paris)
- 25
- 50
- 75
- 100 (Rome)
There are 2 roads from Paris to Rome:
1 -> 50 -> 100
1 -> 50 -> 25 -> 75 -> 100
Input
Line 1: An integer N corresponding to the total number of paths
N next lines: Two integers A and B corresponding to the two cities the path connects.
N next lines: Two integers A and B corresponding to the two cities the path connects.
Output
The number of roads from Paris to Rome
Constraints
1 ≤ N ≤ 100
1 ≤ A,B ≤ 100
1 ≤ A,B ≤ 100
Example
Input
4 1 25 25 50 50 75 75 100
Output
1
Tags
Graphs, Pathfinding
Difficulty
Medium
Test cases
One road Test
Input
4
1 25
25 50
50 75
75 100
Output
1
One road (validator) Validator
Input
2
1 50
50 100
Output
1
Two roads Test
Input
4
50 1
50 100
1 60
60 100
Output
2
Two roads (validator) Validator
Input
4
40 1
40 100
1 50
50 100
Output
2
No way Test
Input
2
1 20
80 100
Output
0
No way (validator) Validator
Input
2
1 30
70 100
Output
0
Oops, loops! Test
Input
13
1 10
1 20
10 20
10 30
20 30
30 40
30 60
50 40
50 60
60 25
50 25
60 70
70 100
Output
12
Oops, loops! (validator) Validator
Input
11
1 25
25 30
25 20
20 30
100 75
75 70
75 80
70 80
25 75
20 70
30 80
Output
9
Big graph! Test
Input
99
88 21
82 76
16 38
80 70
69 39
12 46
77 95
92 20
41 44
8 76
65 49
58 15
62 47
84 60
57 1
9 15
24 90
24 26
20 84
73 58
9 23
5 21
80 94
80 84
80 20
72 59
64 73
77 39
19 45
16 46
84 69
85 79
91 31
100 63
46 6
9 11
88 61
12 86
8 34
15 31
67 22
48 74
76 31
1 87
37 38
83 7
34 45
85 78
85 30
24 49
81 97
43 46
86 63
87 63
88 75
7 79
59 6
40 86
41 37
97 10
42 23
41 39
42 20
70 30
1 2
97 1
64 25
16 79
16 36
33 84
18 67
58 52
38 23
32 67
16 42
17 21
9 44
73 20
11 21
56 14
72 66
73 26
2 84
81 26
96 67
49 43
32 98
44 53
69 23
60 20
2 35
74 35
8 91
82 67
72 29
67 14
66 91
85 62
16 43
Output
863
Big graph! (validator) Validator
Input
99
42 94
88 97
56 27
85 15
51 52
34 43
29 70
64 43
77 30
27 76
81 7
82 14
16 58
40 72
49 67
1 58
40 57
37 22
21 7
72 12
8 57
52 45
80 45
11 52
80 38
30 31
35 77
13 87
64 73
9 36
60 62
61 54
4 5
25 22
1 36
65 22
81 39
57 4
50 12
42 37
61 87
53 31
18 3
28 21
66 70
92 69
26 68
56 11
41 71
42 15
33 92
1 87
97 91
88 55
43 22
90 20
1 22
44 47
40 74
32 86
71 79
32 53
17 31
74 29
66 84
60 46
5 30
100 85
91 95
86 54
65 31
41 85
82 3
77 61
17 20
80 97
4 47
68 4
74 46
57 68
59 94
89 63
41 5
58 6
18 36
37 87
50 98
21 31
83 47
94 22
83 13
44 53
98 30
50 3
82 61
83 60
27 70
64 10
49 15
Output
855
Solution language
Solution
Stub generator input