잔디밭의 개미굴

KOI 공원의 잔디밭에는 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 $N$개의 방으로 구성되어 있다. 서로 다른 두 방을 직접 잇는 통로가 $N - 1$개 있고, 임의의 두 방 사이는 통로를 따라 항상 이동할 수 있다. 즉, 개미굴은 $N$개의 정점으로 이루어진 트리이다. 각 방에는 $1$ 이상 $N$ 이하의 번호가 붙어 있다.

개미굴의 각 방에는 최대 한 마리의 개미가 살 수 있다. 두 개미가 사는 방이 통로로 직접 연결되어 있다면, 두 개미는 서로 불편해한다. 따라서 개미굴의 각 통로가 잇는 두 방 중 최대 한 방에만 개미가 산다.

개미들은 똑똑해서, 이 조건을 만족하는 상태에서 가능한 한 많은 개미가 개미굴에 살고 있다. 다시 말해, 개미굴에 개미 한 마리가 새로 들어온다면 방에 개미를 어떻게 배치하더라도 조건을 만족시킬 수 없다.

화창한 여름날, KOI 공원에는 많은 사람이 소풍을 나오고 있다. 사람들이 잔디밭에서 노는 동안 개미굴을 이루는 흙이 으스러지면서 서로 다른 두 방을 잇는 통로가 정확히 하나 생긴다. 이때 통로가 생기는 두 방은 원래 통로로 직접 연결되어 있었을 수도 있다. 다시 말해, 어떤 두 정수 $1 \le i < j \le N$에 대해 $i$번 방과 $j$번 방을 잇는 통로가 새로 생길 수 있으며, 이는 이전에 두 방을 잇는 통로가 있었는지와 무관하다.

이에 따라 어떤 두 개미가 직접 연결된 방에 살게 되어 서로 불편해지는 쌍이 생길 수 있다. 이 경우 현재 개미들이 배치를 바꾸어 조건을 만족시켜야 할 수도 있다. $(i, j)$의 선택에 따라 이것이 가능한 경우도 있지만, 어떤 경우에는 개미들이 배치를 어떻게 바꾸더라도 조건을 만족시키는 것이 불가능하다. 이때는 살고 있던 개미들이 쫓겨나야 할 수도 있다.

두 정수 $1 \le i < j \le N$에 대해 $i$번 방과 $j$번 방을 잇는 통로가 새로 생겼을 때, 개미들이 아무도 쫓겨나지 않고 적절히 재배치하여 조건을 만족시킬 수 있다면 이것을 평화로운 쌍이라고 하자. 개미굴의 구조가 주어질 때, 평화로운 쌍의 개수를 세어야 한다.

첫 번째 줄에 $N$이 주어진다.

이후 $N-1$개의 줄에 각 통로가 잇는 두 방의 번호 $u$와 $v$가 주어진다.

첫 번째 줄에 평화로운 쌍의 개수를 출력한다.

• $2 \le N \le 250\,000$
• $u \neq v$
• $1 \leq u, v \leq N$
• 주어지는 개미굴은 트리 구조이다.