Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×
E. Том и Джерри
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано неориентированное дерево, состоящее из $$$n$$$ вершин. Простой путь $$$p$$$ длины $$$k$$$ определяется как последовательность различных вершин $$$p_0,p_1,\ldots,p_k$$$ такая, что между вершинами $$$p_i$$$ и $$$p_{i+1}$$$ существует неориентированное ребро для каждого $$$0 \le i \lt k$$$. Простой путь однозначно задаётся неупорядоченной парой своих концов $$$(p_0,p_k)$$$. То есть $$$(u,v)$$$ и $$$(v,u)$$$ представляют один и тот же простой путь.

Том и Джерри играют в игру на этом дереве. Игроки ходят по очереди, первым ходит Том. На $$$i$$$-м ходе ($$$i \ge 1$$$) текущий игрок выбирает простой путь $$$(x_i,y_i)$$$, который удовлетворяет следующим условиям:

  • $$$x_i \ne y_i$$$.
  • Путь не имеет общих рёбер ни с одним из ранее выбранных путей.
  • Либо $$$x_i$$$, либо $$$y_i$$$ принадлежит пути, выбранному на $$$(i-1)$$$-м ходе. Заметим, что это условие применяется только при $$$i \ge 2$$$.

Игрок, который не может выбрать допустимый путь на своём ходе, проигрывает.

Предполагая, что Том и Джерри играют оптимально, ваша задача — вычислить общее количество различных простых путей, которые Том может выбрать на первом ходе так, чтобы он мог гарантировать победу.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных дано целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$), обозначающее количество вершин в дереве.

В каждой из следующих $$$n-1$$$ строк даны два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), обозначающие неориентированное ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что рёбра образуют корректное дерево.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите целое число, обозначающее общее количество различных простых путей, которые Том может выбрать на первом ходе так, чтобы он мог гарантировать победу.

Пример
Входные данные
5
2
1 2
3
1 2
2 3
5
1 2
2 3
2 4
2 5
5
1 2
2 3
3 4
4 5
7
1 2
2 3
2 4
4 5
5 6
5 7
Выходные данные
1
1
6
1
5
Примечание

В первом наборе входных данных дерево состоит только из двух вершин и одного ребра между вершинами $$$1$$$ и $$$2$$$. Том может выбрать простой путь $$$(1,2)$$$ на своём первом ходе. Поскольку этот путь использует единственное ребро в дереве, у Джерри не останется неиспользованных рёбер, чтобы составить допустимый путь на своём ходе. Следовательно, Джерри не сможет сделать ход, и Том выигрывает игру. Для Тома существует ровно $$$1$$$ выигрышный путь.

В третьем наборе входных данных дерево представляет собой звезду с вершиной $$$2$$$ в центре, соединённой с вершинами $$$1, 3, 4,$$$ и $$$5$$$. Всего существует $$$10$$$ возможных простых путей.

Один из выигрышных путей — $$$(1,3)$$$:

  • На своём первом ходе Том выбирает $$$(1,3)$$$. Этот путь использует рёбра $$$(1,2)$$$ и $$$(2,3)$$$, а его вершины — $$$\{1, 2, 3\}$$$. Неиспользованными в дереве остаются рёбра $$$(2,4)$$$ и $$$(2,5)$$$.
  • На ходе Джерри он должен выбрать путь, не пересекающийся по рёбрам с уже выбранными, причём хотя бы один конец должен принадлежать пути Тома $$$\{1, 2, 3\}$$$. Единственные допустимые пути, которые может выбрать Джерри, — это $$$(2,4)$$$ или $$$(2,5)$$$. Джерри не может выбрать путь $$$(4,5)$$$, потому что его концы $$$4$$$ и $$$5$$$ не принадлежат пути Тома $$$\{1, 2, 3\}$$$.
  • Предположим, Джерри выбирает $$$(2,4)$$$. Теперь вершины его пути — $$$\{2, 4\}$$$.
  • На следующем ходе Тома он должен выбрать путь с концом в $$$\{2, 4\}$$$. Он может просто выбрать последний оставшийся путь $$$(2,5)$$$.
  • После этого все рёбра исчерпаны, у Джерри не остаётся ходов, и Том выигрывает.

Один из проигрышных путей — $$$(1,2)$$$:

  • Предположим, Том начинает с выбора $$$(1,2)$$$. Вершины на его пути — $$$\{1, 2\}$$$, а оставшиеся рёбра — $$$(2,3), (2,4),$$$ и $$$(2,5)$$$.
  • Джерри может ответить, выбрав путь $$$(2,3)$$$. Это допустимо, потому что конец $$$2$$$ находится на предыдущем пути Тома. Вершины пути Джерри — $$$\{2, 3\}$$$.
  • Теперь Том вынужден выбрать неиспользованный путь с концом в $$$\{2, 3\}$$$. Он должен выбрать либо $$$(2,4)$$$, либо $$$(2,5)$$$. Пусть он выбирает $$$(2,4)$$$.
  • Тогда Джерри легко выберет последний оставшийся путь $$$(2,5)$$$, поскольку его конец $$$2$$$ принадлежит предыдущему пути Тома $$$\{2, 4\}$$$.
  • Теперь все рёбра использованы. Том не может сделать ход на своём ходе и проигрывает игру.