Alice와 Bob은 두 말을 아래로 떨어뜨리는 게임 All Falls Down을 한다. 게임판은 번 정점을 루트로 하는 트리이며, 각 자식 정점은 부모 정점보다 아래에 있다.
먼저 Alice가 서로 다른 두 정점 를 고르고, 각 정점에 말 하나를 놓는다.
이후 Bob부터 시작하여 두 사람이 번갈아 턴을 진행한다. 자신의 턴에는 각 말이 놓인 정점의 자식을 하나씩 골라 두 말을 동시에 그 자식으로 이동해야 한다. 즉, 두 말을 모두 한 단계 아래로 떨어뜨려야 한다. 두 말 중 하나라도 더 내려갈 수 없다면 그 턴의 사람이 패배한다.
두 사람은 최적으로 행동한다. Alice가 이기는 서로 다른 정점의 순서 없는 쌍 의 개수를 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 케이스마다 Alice가 이기는 정점 쌍의 개수를 한 줄에 출력한다.
각 케이스는 다음과 같은 형식으로 주어진다.
이는 각 에 대해 번 정점과 번 정점을 잇는 간선이 있음을 의미한다.
| 3 | 20 | 트리는 경로이며, 번 정점은 경로의 끝점이다. |
| 4 | 45 | 추가적인 제약이 없다. |
