Prázdny
Prázdny

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.