Олимпиадный тренинг

Задача . E. Количество простых путей

Задача

Темы: графы Деревья Комбинаторика поиск в глубину и подобное *2000

Вам дан неориентированный граф, состоящий из $n$ вершин и $n$ ребер. Гарантируется, что заданный граф является связным (то есть возможно достичь любую вершину из любой другой вершины) и не содержит петель и кратных ребер.

Ваша задача — посчитать количество простых путей длины хотя бы $1$ в заданном графе. Заметьте, что пути, которые отличаются только направлением, являются одинаковыми (то есть вам необходимо посчитать количество неориентированных путей). Например, пути $[1, 2, 3]$ и $[3, 2, 1]$ являются одинаковыми.

Вам необходимо ответить на $t$ независимых наборов тестовых данных.

Напомним, что путем в графе называется такая последовательность вершин $v_1, v_2, \ldots, v_k$, что каждая пара соседних (последовательных) вершин в этой последовательности соединена ребром. Длиной пути является количество ребер в нем. Простым путем называется такой путь, что все вершины в нем различны.

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

Первая строка входных данных содержит одно целое число $t$ ($1 \le t \le 2 \cdot 10^4$) — количество наборов тестовых данных. Затем следуют $t$ наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число $n$ ($3 \le n \le 2 \cdot 10^5$) — количество вершин (и количество ребер) в графе.

Следующие $n$ строк набора тестовых данных описывают ребра: ребро $i$ задано парой вершин $u_i$, $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), где $u_i$ и $v_i$ — это вершины, которые соединяет $i$-е ребро. Для каждой пары вершин $(u, v)$ существует не более одного ребра между $u$ и $v$. Не существует ребер из вершины в саму себя. Таким образом, в графе отсутствуют петли и кратные ребра. Граф является неориентированным, то есть все его ребра являются двунаправленными. Граф является связным, то есть всегда возможно достичь любую вершину из любой другой вершины, двигаясь по ребрам графа.

Гарантируется, что сумма $n$ не превосходит $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).

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

Выведите одно целое число для каждого набора тестовых данных: количество простых путей длины хотя бы $1$ в заданном графе. Заметьте, что пути, которые отличаются только направлением, являются одинаковыми (то есть вам необходимо посчитать количество неориентированных путей).

Примечание

Рассмотрим второй набор тестовых данных примера. Он выглядит следующим образом:

$\text{[math]}$