D. Соединение конфликтов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Деревом называется связный граф без циклов. Определим независимое множество дерева как множество вершин, в котором никакие две различные вершины не соединены ребром дерева напрямую. Наибольшее независимое множество — это независимое множество, содержащее максимально возможное количество вершин.

Дан лес из $$$k$$$ деревьев, в который требуется добавить $$$k-1$$$ рёбер, чтобы объединить лес в одно дерево и максимизировать размер наибольшего независимого множества получившегося дерева. Найдите добавляемые рёбра.

Если существует несколько допустимых ответов, можно вывести любой из них.

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

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

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

Далее следует описание каждого из $$$k$$$ деревьев, пронумерованных по порядку числами $$$1, 2, \ldots, k$$$:

Первая строка содержит одно целое число $$$n$$$ ($$$1\le n \le 2 \cdot 10^5$$$) — размер дерева. Вершины дерева пронумерованы целыми числами от $$$1$$$ до $$$n$$$.

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

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

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

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

Для каждого набора входных данных выведите $$$k-1$$$ строк, каждая из которых содержит четыре целых числа $$$t_1, v_1, t_2, v_2$$$, обозначающих ребро между $$$(t_1,v_1)$$$ и $$$(t_2,v_2)$$$, добавляемое к исходному графу.

Обратите внимание, что все $$$k$$$ деревьев пронумерованы числами от $$$1$$$ до $$$k$$$ в порядке, в котором они даны во входных данных. Для любого дерева $$$i$$$ ($$$1\le i \le k$$$), содержащего $$$n$$$ вершин, его вершины пронумерованы числами от $$$1$$$ до $$$n$$$. Вершина с номером $$$j$$$ в этом дереве обозначается как $$$(i,j)$$$.

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

В первом наборе входных данных граф содержит две вершины и не содержит рёбер; добавление ребра между этими двумя вершинами — единственный способ превратить граф в дерево.

Во втором наборе входных данных можно добавить ребро между единственной вершиной $$$1$$$ дерева $$$2$$$ и одной из вершин $$$1$$$, $$$2$$$ и $$$3$$$ дерева $$$1$$$.

  • Если добавить ребро $$$(2,1)-(1,1)$$$, размер наибольшего независимого множества получившегося дерева равен 3.
  • Если добавить ребро $$$(2,1)-(1,2)$$$, размер наибольшего независимого множества получившегося дерева равен 2.
  • Если добавить ребро $$$(2,1)-(1,3)$$$, размер наибольшего независимого множества получившегося дерева равен 2.

Поэтому выберем ребро $$$(2,1)-(1,1)$$$, так как оно оптимально.