Back
Close
  • 45

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

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.
Output
The number of roads from Paris to Rome
Constraints
1 ≤ N ≤ 100
1 ≤ A,B ≤ 100
Example
Input
4
1 25
25 50
50 75
75 100
Output
1

A higher resolution is required to access the IDE