Grass Cownoisseur#11194

Grass Cownoisseur

1 second

128 megabytes

Very hard

In an effort to better manage the grazing patterns of his cows, Farmer John has installed one-way cow paths throughout his farm. The farm consists of $n$ fields, conveniently numbered from $1$ to $n$ , with each one-way path connecting a pair of fields. For example, if a path connects field $x$ to field $y$ , cows may travel from $x$ to $y$ , but not from $y$ to $x$ .

Bessie the cow, as we all know, enjoys eating grass in as many fields as possible. She always starts in field $1$ at the beginning of the day and follows a route that eventually returns to field $1$ at the end of the day. She wants to maximize the number of distinct fields along her route, since she gets to eat the grass in each one. If she visits a field multiple times, she only eats the grass there once.

As one might imagine, Bessie is not particularly happy about the one-way restriction on FJ's paths, since it limits the number of distinct fields she can visit during her daily route. She wonders how much grass she could eat if she were allowed to break the rules and travel along at most one path in the wrong direction.

Please determine the maximum number of distinct fields Bessie can visit along a route that starts and ends at field $1$ , given that she may travel along at most one path in the wrong direction. Bessie may travel in the wrong direction at most once during her entire journey. In particular, she cannot travel backward along the same path more than once.

Input

The first line contains $n$ and $m (1 \leq n, m \leq 1 0^{5})$ m~(1 \le n, m \le 10^5), the number of fields and the number of one-way paths, respectively.

The following $m$ lines each describe a one-way cow path. Each line contains two distinct field numbers $x$ and $y$ , indicating that cows may travel from field $x$ to field $y$ . No path appears more than once in the input.

Output

Print one integer — the maximum number of distinct fields Bessie can visit along a route that starts and ends at field $1$ , given that she may travel along at most one path in the wrong direction.

Examples

Example 1

Note

Bessie can visit fields $1, 2, 4, 7, 2, 5, 3$ 1, 2, 4, 7, 2, 5, 3, and $1$ by traveling backward along the path between $5$ and $3$ . However, once she reaches field $3$ , she cannot reach field $6$ without traveling backward along another path.

v---3-->6
7   |\  |
^\  v \ |
| \ 1  \|
|  \|   v
|   v   5
4<--2---^