Background

USACO January 2019 Contest, Platinum Problem 2.

Problem Description

The cow Bessie realizes that in order to stay in good shape, she needs to exercise more. She needs your help choosing a route on the farm for her morning run each day. The farm consists of $n$ pastures, numbered $1 \sim n$ for convenience, connected by $m$ undirected paths. As creatures of habit, the cows tend to use a specific set of $n - 1$ paths as their daily routes for moving between pastures—these are called the “regular” paths. From any pasture, it is possible to reach every other pasture using only regular paths.

To make her morning run more interesting, Bessie thinks she should choose a route that includes some non-regular paths. However, using regular paths makes her feel comfortable, so she does not want to use too many non-regular paths in her route. After some thought, she decides that a good route should form a simple cycle (returning to the starting point without visiting any pasture more than once), and it must contain exactly two non-regular paths.

Please help Bessie compute the number of good routes she can take. Two routes are considered the same if they contain the same set of paths.

Input Format

The first line contains $n$ and $m$. The next $m$ lines each contain two integers $a_i$ and $b_i$, describing the endpoints of a path. The first $(n - 1)$ paths are regular paths.

Output Format

Output one line with an integer representing the total number of routes Bessie can choose.

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

4

Hint

Constraints

For all test cases, it is guaranteed that $1 \leq n \leq 2 \times 10^5$, $1 \leq m \leq 2 \times 10^5$, $m \geq n - 1$, and $1 \leq a_i, b_i \leq n$.

Translated by ChatGPT 5