Exercise Route

题目描述

奶牛 Bessie 意识到她需要多锻炼以保持良好的体型。她需要你帮忙在农场周围选择一些潜在路线，用作早晨慢跑。 农场由 $N$ 块田地组成（$1 \leq N \leq 2 \cdot 10^5$），方便地编号为 $1 \ldots N$，并通过 $M$ 条双向小道连接（$1 \leq M \leq 2 \cdot 10^5$）。由于习惯使然，奶牛们在田地间日常移动时总是使用其中一个由 $N-1$ 条小道构成的特定子集——它们称这些为“标准”小道。只使用标准小道就可以从任意一块田地到达任意另一块田地。 为了让晨跑更有趣，Bessie 决定选择一条包含一些非标准小道的路线。然而，她对使用标准小道非常适应，因此不想在路线中使用太多非标准小道。经过思考，她认为一条好的路线应当形成一个简单环（回到起点，且不重复经过任何田地），并且恰好包含两条非标准小道。 请帮助 Bessie 统计她可以使用的好路线数量。若两条路线包含相同的一组小道，则认为它们相同。

输入格式

第一行包含 $N$ 和 $M$。接下来 $M$ 行中，每行包含两个整数 $a_i$ 和 $b_i$，描述一条小道的两个端点。其中前 $N-1$ 条为标准小道。

输出格式

输出 Bessie 可能想使用的路线总数。

5 8
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 2

4

提示

题目致谢：Dhruv Rohatgi

标签: USACO|2019|Platinum

来源

USACO|2019|Platinum