운동 경로

시간 제한2초메모리 제한512 MB

요약

N개의 밭을 잇는 표준 산책로 트리와 추가 산책로가 주어질 때, 추가 산책로를 정확히 두 개 포함하는 단순 사이클의 개수를 구합니다.

난이도: 보통10점 중 7점
유형: 트리, 유니온 파인드, 정렬
정답자: 아직 제출이 없습니다

문제

베시는 건강을 유지하려면 운동을 더 해야 한다고 생각한다. 그녀가 아침 조깅에 쓸 농장 내 경로를 고를 수 있도록 도움이 필요하다.

농장은 $N$ 개의 밭( $1 \leq N \leq 2 \cdot 10^5$ )으로 이루어져 있으며, 1부터 $N$ 까지 번호가 매겨져 있다. 밭들은 $M$ 개의 양방향 길( $1 \leq M \leq 2 \cdot 10^5$ )로 연결되어 있다. 소들은 습관적으로 $N-1$ 개의 길만 사용해 밭 사이를 이동한다. 이 길들을 '표준' 길이라고 부른다. 표준 길만으로 어떤 밭에서든 다른 모든 밭으로 갈 수 있다.

베시는 비표준 길을 일부 포함하는 경로를 원하지만, 너무 많이 쓰고 싶지는 않다. 좋은 경로는 단순 사이클(출발점으로 돌아오며, 같은 밭을 두 번 지나지 않는 경로)이면서 비표준 길을 정확히 두 개 포함하는 경로이다. 베시가 택할 수 있는 좋은 경로의 개수를 세어라. 사용하는 길의 집합이 같으면 같은 경로로 본다.

입력

첫 줄에 $N$ 과 $M$ 이 주어진다. 다음 $M$ 개 줄에는 길의 양 끝점 $a_i$ , $b_i$ 가 주어진다. 처음 $N-1$ 개의 길이 표준 길이다.

출력

베시가 이용할 수 있는 경로의 총 개수를 출력한다.

예제1

예제 1
입력
```
5 8
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 2
```
예상 출력
```
4
```