A. Interesting Paths
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

We are given a directed graph with $$$n$$$ vertices and $$$m$$$ edges. The vertices of the graph are numbered from $$$1$$$ to $$$n$$$, and each edge leads from a vertex with a smaller number to a vertex with a larger number.

We call a sequence of paths interesting if:

  • each path starts at vertex $$$1$$$ and ends at vertex $$$n$$$,
  • each path contains at least one edge that was not present in any of the previous paths.

What is the length of the longest interesting sequence of paths?

Input

The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n\leq 10^6$$$, $$$0 \leq m \leq 10^6$$$), denoting the number of vertices and edges of the considered graph.

Each of the next $$$m$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a \lt b \leq n$$$) describing a directed edge leading from vertex $$$a$$$ to vertex $$$b$$$. Each pair $$$(a,b)$$$ appears in the input at most once.

Output

The output should contain a single integer - the maximum length of the interesting sequence of paths.

Examples
Input
5 7
1 3
3 5
1 2
2 3
3 4
4 5
2 4
Output
4
Input
5 3
1 3
2 3
2 5
Output
0
Note

For the first example, an interesting sequence of paths of length $$$4$$$ may look as follows:

  • $$$1 \rightarrow 3 \rightarrow 5$$$ (the edge $$$1 \rightarrow 3$$$ was used for the first time),
  • $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 5$$$ (the edge $$$1 \rightarrow 2$$$ was used for the first time),
  • $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 5$$$ (the edge $$$3 \rightarrow 4$$$ was used for the first time),
  • $$$1 \rightarrow 2 \rightarrow 4 \rightarrow 5$$$ (the edge $$$2 \rightarrow 4$$$ was used for the first time).
In the second example, there is no path from vertex $$$1$$$ to vertex $$$5$$$.