USACO 2019 January Contest Platinum Problem 2 Exercise Route

Bessie the cow realizes she needs to exercise more in order to stay in good shape. She needs your help selecting potential routes around the farm that she can use for her morning jogging routine.

The farm is made up of NN fields (1≤N≤2⋅1051≤N≤2⋅105), conveniently numbered 1…N1…N, and conveniently connected by a set of MM bi-directional trails (1≤M≤2⋅1051≤M≤2⋅105). Being creatures of habit, the cows tend to use one particular subset of N−1N−1 trails for all of their daily movement between fields -- they call these the "standard" trails. It is possible to travel from any field to any other field using only standard trails.

To keep her morning jog interesting, Bessie decides that she should pick a route that involves some non-standard trails. However, she is so comfortable with using standard trails, she doesn't want to use too many non-standard trails on her route. After some thought, she decides a good route is one that forms a simple cycle (returning to its starting point, and not using any field more than once) that contains exactly two non-standard trails.

Please help Bessie count the number of good routes she can use. Two routes are considered the same if they involve the same set of trails.

OUTPUT FORMAT (file exercise.out):

Output the total number routes Bessie might want to use.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4

Problem credits: Dhruv Rohatgi

以上就是关于【USACO 2019 January Contest Platinum Problem 2 Exercise Route】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

USACO样例通过提交错误怎么办？从边界测试到复杂度逐步排查！

10月20日截止！2026年CAICP人工智能能力认证，第一轮即将截止！