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

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

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

개미들은 똑똑하기 때문에, 이 조건을 만족하는 하에 최대한 많은 개미들이 현재 개미굴에 살고 있다. 다시 말해, 현재 개미굴에 한 마리의 개미가 새롭게 들어온다면, 개미굴의 각 방에 개미를 어떻 게 배치하더라도 위 조건을 만족시킬 수 없다.

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

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

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