Grass Cownoisseur

题目描述

为了更好地管理奶牛的放牧路线，农夫 John 在他的农场里修建了许多单向的牛道。农场由 $N$ 个草场组成，编号为 $1..N$，每条单向牛道连接一对草场。例如，如果一条道路从草场 $X$ 通向草场 $Y$，那么奶牛可以从 $X$ 走到 $Y$，但不能从 $Y$ 走到 $X$。\n\n众所周知，奶牛 Bessie 喜欢尽可能多地在不同草场吃草。她每天一开始总是在草场 $1$，走过一串草场，并在一天结束时回到草场 $1$。她试图最大化路线中经过的不同草场数量，因为每个草场她都能吃到草（如果多次到访同一草场，她只会吃一次）。\n\n可以想象，Bessie 对这些道路的单向限制并不满意，因为这很可能会减少她每天路线中能访问到的不同草场数量。她想知道，如果她违反规则，在路线中最多沿着一条道路反方向行走一次，她最多能吃到多少草。请计算：在一条从草场 $1$ 出发并回到草场 $1$ 的路线中，允许最多有一条道路被反方向走过的情况下，Bessie 能访问到的不同草场的最大数量。Bessie 在整个旅程中最多只能反向行走一次；特别地，她甚至不能把同一条道路反向走两次。

输入格式

第一行输入包含 $N$ 和 $M$，分别表示草场数量和单向道路数量（1 <= N, M <= 100,000）。\n\n接下来 $M$ 行每行描述一条单向牛道。每行包含两个不同的草场编号 $X$ 和 $Y$，表示一条从 $X$ 到 $Y$ 的牛道。同一条牛道不会出现多次。

输出格式

输出一行，表示在从草场 $1$ 出发并回到草场 $1$ 的路线中，且在该路线中最多允许一条道路按反方向行走的情况下，Bessie 能访问到的不同草场的最大数量。

7 10\n1 2\n3 1\n2 5\n2 4\n3 7\n3 5\n3 6\n6 5\n7 2\n4 7

6

提示

【解题说明】\n\n下面是样例输入的 ASCII 图示：\n\nv---3-->6\n7 |\ |\n^\ v \ |\n| \ 1 |\n| | v\n| v 5\n4<--2---^\n\nBessie 可以按 1, 2, 4, 7, 2, 5, 3, 1 的顺序访问草场，方法是在 5 和 3 之间的道路上反向行走。当她到达 3 时，如果不再走另一条反向道路，她就无法到达 6。

标签: USACO|2015|Gold

来源

USACO|2015|Gold