레이팅 미적용소 베시는 건강을 유지하려면 운동을 더 해야 한다는 것을 깨달았다. 아침 조깅 루틴에 사용할 수 있는 농장 주변의 잠재적 경로를 고르는 일을 도와주자.
농장은 \(N\)개의 밭 (\(1 \leq N \leq 2 \cdot 10^5\))으로 이루어져 있으며, 편의상 \(1 \ldots N\)번으로 번호가 매겨져 있고, 편리하게도 \(M\)개의 양방향 오솔길 (\(1 \leq M \leq 2 \cdot 10^5\))로 연결되어 있다. 습관의 동물인 소들은 밭 사이의 일상적인 이동에 특정한 \(N-1\)개의 오솔길 부분집합만 사용하는 경향이 있다 -- 소들은 이를 "표준" 오솔길이라고 부른다. 표준 오솔길만 사용해서 어떤 밭에서든 다른 어떤 밭으로도 이동할 수 있다.
아침 조깅을 흥미롭게 유지하기 위해, 베시는 비표준 오솔길을 일부 포함하는 경로를 골라야겠다고 결심한다. 하지만 표준 오솔길에 너무 익숙해진 나머지, 경로에 비표준 오솔길을 너무 많이 쓰고 싶지는 않다. 고민 끝에 베시는 정확히 두 개의 비표준 오솔길을 포함하는 단순 사이클 (시작점으로 돌아오고, 어떤 밭도 두 번 이상 사용하지 않는 경로)을 이루는 경로가 좋은 경로라고 결정한다.
베시가 사용할 수 있는 좋은 경로의 개수를 세도록 도와주자. 같은 오솔길 집합을 사용하는 두 경로는 같은 경로로 간주한다.
출제자: Dhruv Rohatgi
출제자: Dhruv Rohatgi
첫째 줄에 \(N\)과 \(M\)이 주어진다. 다음 \(M\)개의 줄에는 각각 오솔길의 양 끝점을 나타내는 두 정수 \(a_i\)와 \(b_i\)가 주어진다. 이 중 처음 \(N-1\)개가 표준 오솔길이다.
베시가 사용하고 싶어할 수 있는 경로의 총 개수를 출력한다.
exercise.in · 출력을 쓸 파일 exercise.out5 8
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 24riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > January > Platinum