今天 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