Time to Explore Taohua Island

After passing Huang Yaoshi's test, you are free to explore Taohua Island! You must start your journey at the western end of the island and travel to the eastern end. At the eastern dock, you leave but then if you wish to experience the beautiful scenery again, you can take a boat from the eastern dock back to the western end to explore a new route. However, there is one rule on Taohua Island: although you can traverse the island as many times as you want, no two routes can use exactly the same set of roads.

The island is modeled as a directed acyclic graph (DAG) with n intersections (nodes) and m directed roads (edges). There may be multiple roads between the same pair of intersections. The journey always starts at the western end (node 1) and ends at the eastern end (node n), and at least one route exists between these two endpoints.

For each distinct route p from node 1 to node n, let \( \ell(p) \) denote the number of roads (edges) used, which represents the time (in arbitrary time units) spent on that route. Your task is to calculate the total time needed to traverse all distinct routes, i.e., compute

where \( \mathcal{P} \) is the set of all distinct paths from node 1 to node n. Two routes are considered different if and only if the sets of roads used are not exactly the same.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10⁵ perhaps) representing the number of intersections and roads respectively.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n) indicating there is a directed road from intersection u to intersection v.

The graph is guaranteed to be acyclic, and there exists at least one route from node 1 (western end) to node n (eastern end).

outputFormat

Output a single integer, which is the total time required to travel all distinct routes from node 1 to node n. Each road traversal takes 1 unit of time.

sample

4 4
1 2
2 4
1 3
3 4

4