KOI 공원의 잔디밭에는 여러 개미가 모여 사는 개미굴이 있다.

개미굴은 N개의 방으로 구성되어 있으며, 서로 다른 두 개미굴을 직접 잇는 N -1개의 통로가 있고,
임의의 서로 다른 두 개미굴 사이를 통로들을 통해서 항상 이동할 수 있다.

즉, 개미굴은 N개의 정점으로 구성된 트리이다. 각 방에는 1 이상 N 이하의 번호가 붙어 있다.

개미굴의 각 방에는 최대 한 마리의 개미가 살 수 있다.

만약에 두 개미가 사는 방이 통로로 직접 연결되어 있다면, 두 개미는 서로 불편해한다.

따라서, 현재 개미굴의 각 통로가 연결하는 두 방 중, 최대 한 방에만 개미가 살고 있다.

개미들은 똑똑하기 때문에, 이 조건을 만족하는 하에 최대한 많은 개미들이 현재 개미굴에 살고 있다.

다시 말해, 현재 개미굴에 한 마리의 개미가 새롭게 들어온다면, 개미굴의 각 방에 개미를 어떻 게 배치하더라도 위 조건을 만족시킬 수 없다.

화창한 여름날, KOI 공원에는 많은 사람들이 소풍을 나오고 있다.

사람들이 잔디밭에서 소풍을 즐기다 보면, 개미굴을 이루는 흙이 으스러지면서 서로 다른 두 방을 잇는 통로가 정확히 하나 생긴다.

이때 통로가 생기는 두 방은 원래도 통로로 직접 연결된 방일 수 있다.

다시 말해, 어떠한 두 정수 1 \le i \lt j \le N 에 대해, i 번 방과 j 번 방을 잇는 통로가 새롭게 생길 수 있으며,
이는 이전에 i 번 방과 j 번 방을 잇는 통로가 있었는지 여부와 무관하다.

이렇게 통로가 생김에 따라, 어떠한 두 개미가 사는 방이 직접 연결되면서 불편해지는 개미의 쌍이 생기게 될 수 있다.

이에 따라 현재 개미굴에 살고 있는 개미들이 배치를 바꾸어서 조건을 만족시켜 야 할 수도 있다.

(i, j) 의 선택에 따라서 이것이 가능한 경우도 있지만,
어떤 경우에는 현재 살고 있는 개미들이 어떻게 배치를 바꾸더라도 조건을 만족시키는 것이 불가능할 수도 있다.

이러한 경우 에는 살고 있던 개미들이 쫓겨나야 할 수도 있다.

만약 어떠한 두 정수 1 \le i \lt j \le N에 대해, i 번 방과 j번 방을 잇는 통로가 새롭게 생길 때,
개미들이 아무도 서로를 쫓아내지 않고 적절한 재배치를 통해 조건을 만족시킬 수 있다면 이것을 평화로운 쌍 이라고 하자.

개미굴의 구조가 주어질 때, 당신은 평화로운 쌍 의 개수를 세어야 한다.

잔디밭의 개미굴 timer 2s memory 1024MB

잔디밭의 개미굴 2s 1024MB