Alice와 Bob은 그래프에서 말을 옮기는 게임 All Falls Somewhere를 한다. 게임판은 개의 정점과 개의 무방향 간선으로 이루어진 연결 그래프이다. 정점에는 부터 까지 번호가 붙어 있으며, 처음에는 각 정점에 말이 하나씩 놓여 있다.
먼저 Alice가 자신의 정점 를 고르고, 그다음 Bob이 자신의 정점 를 고른다. 두 정점은 서로 달라야 한다.
이후 게임은 개의 턴 동안 진행된다. 홀수 번째 턴에는 Alice가, 짝수 번째 턴에는 Bob이 행동한다. 번째 턴에 행동하는 사람은 정점 와 인접한 정점 하나를 고른 뒤, 정점 에 있는 모든 말을 고른 정점으로 옮긴다.
모든 턴이 끝난 뒤 Alice의 점수는 정점 에 있는 말의 수이고, Bob의 점수는 정점 에 있는 말의 수이다. Alice는 Alice의 점수에서 Bob의 점수를 뺀 값을 최대화하고, Bob은 이 값을 최소화하도록 행동한다.
두 사람이 최적으로 행동할 때 Alice의 점수가 Bob의 점수보다 커지는 서로 다른 정점의 순서 있는 쌍 의 개수를 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 조건을 만족하는 순서 있는 쌍 의 개수를 한 줄에 출력한다.
각 테스트 케이스는 다음과 같은 형식으로 주어진다.
각 는 정점 와 정점 를 잇는 무방향 간선을 나타낸다. 그래프에는 자기 자신을 잇는 간선과 중복 간선이 없으며, 그래프는 연결되어 있다.
