Migrated from Lutece 3180 模拟宇宙·其二

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在移除了分裂金币之后，黑塔终于可以随心所欲的设计模拟宇宙的地图了。

这次的模拟宇宙仍然由 $n$ 个区域和 $m$ 条连接它们的单向通道组成，但不同的是，你可以多次经过一个相同的区域。

由于这次的起点与终点都在1号区域，黑塔特意准备了一个奇物“逆转器”，你可以使用它逆向通过一条道路，效果触发1次后该奇物损毁。你可以在任意时刻使用它甚至不使用它。

现在，你希望知道，如果从1号区域开始这次模拟宇宙，并最终回到1号区域，最多可以经过多少个不同的区域。

Input

第一行两个整数 $n$ 和 $m$ ，分别表示区域的数量和通道的数量。

接下来 $m$ 行，每行两个整数 $u_i$ 和 $v_i$ ，表示区域 $u_i$ 存在一条通道通向区域 $v_i$ 。

Output

一个整数，表示在至多逆转一条通道的方向下最多可以经过的区域数量。

Samples

6 9
1 2
2 4
2 5
3 1
3 4
3 5
3 6
4 2
6 5

5

Constraints

$1 \leq n, m \leq 100000$

$1 \leq u_i, v_i \leq n$

Resources

2024 UESTC ICPC Training for Graph