← 返回题目列表

Codeforces · 687/E

E. 飞行时间

中文机器翻译题面 查看原题

今天 Pari 给 Arya 出了一道很酷的图表问题。 Arya 为其写了一个非最优解,因为他相信自己有能力优化非最优解。除了非优化之外,他的代码还有 bug,而且他尝试了很多优化,所以代码也变脏了!他不断收到超出时间限制的信息,这让他很失望。突然,他的脑海中浮现出了一个好主意!

这是他的肮脏代码的样子:

他要求你编写 TOF 函数,以便优化代码的运行时间,同时最大限度地减少 dfs 函数的调用次数。输入是有向图,在 TOF 函数中,您必须重新排列每个顶点的邻居列表中的图的边。 dfs函数的调用次数取决于每个顶点的邻居的排列。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 5000) - 输入图中的顶点数和有向边数。

接下来的 m 行中的每一行都包含一对整数 ui 和 vi (1 ≤ ui, vi ≤ n),这意味着输入图中存在一条有向 $$u_i \rightarrow v_i$$ 边。

您可以假设该图不会包含任何自循环,并且任何无序顶点对之间最多有一条边。

输出

打印一个整数——通过排列边可以实现的最小可能的 dfs 调用数量。

示例

输入 #1

3 3
1 2
2 3
3 1

输出 #1

2998

输入 #2

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

输出 #2

3001