Task 3 will be revealed 18.11.2026 at 18:00 CET
Login required
From Rookie to Formula 1
Country hint
The first three winners at our track were Nelson Piquet, Nelson Piquet and Ayrton Senna. Find the country!
Problem
Every Formula 1 driver starts their career as a complete beginner. To become a professional driver, they have to complete various driving trainings, simulator exercises and races.
During the training process, there may be several possible choices. For example, a particular driving skill may be acquired through different training sessions, or a driver may reach a particular race through several different routes.
Each possible training or race is represented by a node. A driver can move from one node to another if a directed connection between the two nodes exists.
The complete training system is represented by a directed graph.
Node 1 represents the complete beginner, while node N represents the professional Formula 1 driver.
A development path is valid if it:
- starts at node 1,
- follows an existing directed edge at every step,
- eventually reaches node N.
The training system contains no circular progression, therefore the graph is acyclic.
Your task
Determine how many different ways a complete beginner can become a professional Formula 1 driver.
Two paths are considered different if they contain different nodes at any point.
Input
The first line contains two integers:
N M
where:
- N – the number of nodes,
- M – the number of directed edges.
The nodes are numbered from 1 to N.
Each of the following M lines contains two integers:
A B
This means that it is possible to move directly from node A to node B.
The input guarantees that:
- the graph is directed;
- the graph contains no cycles;
- there is at least one path from node 1 to node N.
Output
Print one integer: the number of different paths from node 1 to node N.
Important
The number of paths may be larger than the maximum value of a 32-bit integer.
According to the constraints, the solution must be able to handle at least 64-bit integer values.
Examples
Example 1
Here you can find an example input:
4 5
1 2
1 3
2 4
3 4
2 3
and here is the example result:
3
because you can go from the point 1 to the point 4 in 3 different ways.
Example 2
Here you can find an other example input:
10 16
1 2
1 3
1 4
2 5
2 6
3 5
3 6
3 7
4 6
4 7
5 8
6 8
6 9
7 9
8 10
9 10
and here is the example result:
10
because you can go from the point 1 to the point 10 in 10 different ways.
Your task:
Read input file and into the field with the answer, enter :
- the resulting values
- the country, which the story refers to
- at the end paste the source code of your program.
.
Input file
Click HERE to download the input file.
Output
You can download the correct result HERE.