Grass Cownoisseur

Problem Source

USACO 2015 January

Problem Description

John has $n$ pastures, numbered $1$ through $n$, connected by several one-way roads. Bessie the cow is a connoisseur of fine grass, and she wants to visit as many pastures as possible to taste the grass.

Bessie always starts from pasture $1$ and finally returns to pasture $1$. She wants to visit as many distinct pastures as possible (a pasture visited many times still counts only once). Because the roads are one-way, this causes Bessie a lot of inconvenience. Bessie would like to secretly walk backwards along one road, but she can do this at most once. What is the maximum number of pastures Bessie can reach?

Input Format

The first line contains two integers $n, m(1\leq n,m \leq 10^5)$.

The following $m$ lines each contain $x$ and $y$, indicating a one-way edge from $x$ to $y$. No road appears more than once.

Output Format

Output one number: the maximum number of pastures Bessie can visit if she may walk backwards along at most one road.

Sample Input

7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7

Sample Output

6

Constraints

$1\leq n,m \leq 10^5$.

Hint

• Use strongly connected components to compress the graph into a DAG, then consider the effect of reversing exactly one edge: it can only help by letting you leave a component you normally cannot and re-enter pasture 1's component. Try reversing each bridge-like edge, or equivalently run longest-path DP forwards and backwards from the component of pasture 1.