#PU901. USACO 2019 January Contest, Platinum — Problem 2. Exercise Route

    ID: 1523 传统题 文件IO:exercise 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan19来源:usaco.orgscoring:equal_test_cases倍增

USACO 2019 January Contest, Platinum — Problem 2. Exercise Route

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 \leq N \leq 2 \cdot 10^5), conveniently numbered 1…N1 \ldots N, and conveniently connected by a set of MM bi-directional trails (1≤M≤2⋅1051 \leq M \leq 2 \cdot 10^5). 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.

输入格式

The first line contains NN and MM. Each of the next MM lines contains two integers aia_i and bib_i describing the endpoints of a trail. The first N−1N-1 of these are the standard trails.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 8
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 2
4
Problem credits: Dhruv Rohatgi