P3119 [USACO15JAN] Grass Cownoisseur G

题目描述

为了更好地管理牛群的放牧路线，Farmer John 在他的农场中安装了若干单向牛道。农场由 $N$ 块草场组成，编号为 $1$ 到 $N$，每条单向牛道连接一对草场。例如，若存在一条从草场 $X$ 到 $Y$ 的路径，则牛可以从 $X$ 前往 $Y$，但不能从 $Y$ 返回 $X$。

众所周知，Bessie 喜欢尽可能多地品尝不同草场的牧草。她每天从草场 $1$ 出发，访问一系列草场后返回草场 $1$。她试图最大化沿途经过的不同草场数量（重复访问的草场只算一次）。

由于单向路径的限制，Bessie 担心这会减少她每日路线中可以访问的草场数量。她想知道如果她违反规则，在路线中最多逆向通过某条道路一次，最多能品尝多少草场的牧草。请计算她从草场 $1$ 出发并返回的情况下，最多能访问的不同草场数量。注意 Bessie 在整个旅程中最多只能逆向通过一条道路，且同一条路径不能逆向两次。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示草场数量和单向牛道数量（$1 \leq N, M \leq 100,000$）。

接下来 $M$ 行每行描述一条单向牛道，包含两个不同的整数 $X$ 和 $Y$，表示从 $X$ 到 $Y$ 的单向路径。保证每条路径不会重复出现。

输出格式

输出一行，表示 Bessie 在最多逆向通过一条道路的情况下，从草场 $1$ 出发并返回时能访问的最大不同草场数量。

输入输出样例 1

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

6

说明/提示

样例解析：

以下是样例输入的 ASCII 图示：

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

Bessie 可以通过逆向路径 $5\to 3$ 访问草场 $1, 2, 4, 7, 2, 5, 3, 1$。到达草场 $3$ 后，若不再次逆向其他路径则无法前往 $6$。