32408번 - 대전 도시철도 2호선

문제

대전시는 $N$개의 교차로와 $N-1$개의 도로가 교차로를 정점, 도로를 간선으로 하는 트리 구조를 이루고 있다. 교차로는 1ドル$번부터 $N$번까지 번호가 매겨져 있다. 대전시는 1ドル$번 교차로와 $N$번 교차로를 잇는 경로를 따라 대전 도시철도 1호선을 운행하고 있다. 이 경로에 포함되는 교차로와 도로에는 각각 역과 철도가 설치되어 있다.

대전시는 도시철도 2호선을 추가로 운행하려고 한다. 1호선과 비슷하게 2호선도 $S$번 교차로와 $E$번 교차로를 잇는 경로를 따라 역과 철도를 설치하려고 한다. $S$번과 $E$번 교차로는 1호선 역이 설치되지 않은 서로 다른 교차로여야 하고, 이용객이 1호선으로 환승할 수 있도록 2호선은 1호선 역을 적어도 하나 포함해야 한다.

대전 도시철도 2호선을 운행하기 위해 조건을 만족하는 두 교차로를 고르는 경우의 수를 구해보자. 단, 두 교차로의 순서를 바꾼 것은 같은 경우로 본다.

입력

첫째 줄에 정수 $N(4\le N\le 100,円 000)$이 주어진다.

둘째 줄부터 $N-1$개의 줄에 도로가 연결하는 양 끝 교차로의 번호 $u,v(1\le u,v\le N;u\neq v)$가 공백으로 구분되어 주어진다.

출력

조건을 만족하는 두 교차로를 고르는 경우의 수를 출력한다.

제한

힌트