B. Омкар и божественное дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лорд Омкар хотел бы, чтобы у него было дерево с $$$n$$$ вершинами ($$$3 \le n \le 10^5$$$), и попросил своих учеников построить дерево. Однако Лорд Омкар создал $$$m$$$ ($$$\mathbf{1 \le m < n}$$$) ограничений, чтобы гарантировать, что дерево будет настолько божественным, насколько это возможно.

Дерево на $$$n$$$ вершинах — это связный неориентированный граф с $$$n$$$ вершинами и $$$n-1$$$ ребром. Заметим, что для любых двух вершин существует ровно один простой путь между ними, где простой путь — это путь между двумя вершинами, который не содержит ни одной вершины более одного раза.

Вот пример дерева:

Ограничение состоит из $$$3$$$ попарно различных целых чисел, $$$a$$$, $$$b$$$ и $$$c$$$ ($$$1 \le a,b,c \le n$$$). Оно означает, что вершина $$$b$$$ не может лежать на простом пути между вершинами $$$a$$$ и $$$c$$$.

Сможете ли вы помочь Лорду Омкару и стать его самым доверенным учеником? Вам нужно будет найти божественные деревья для нескольких наборов ограничений. Можно показать, что при ограничениях задачи божественное дерево всегда найдется.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \leq n \leq 10^5$$$, $$$\mathbf{1 \leq m < n}$$$), представляющих размер дерева и количество ограничений.

$$$i$$$-я из следующих $$$m$$$ строк содержит три целых числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ ($$$1 \le a_i, b_i, c_i \le n$$$, $$$a$$$, $$$b$$$, $$$c$$$ попарно различны), обозначающие, что вершина $$$b_i$$$ не может лежать на простом пути между вершинами $$$a_i$$$ и $$$c_i$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$

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

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

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

Вывод первого набора входных данных соответствует следующему дереву:

Для первого ограничения, простой путь между $$$1$$$ и $$$3$$$ — это $$$1, 3$$$, и не содержит $$$2$$$. Простой путь между $$$3$$$ и $$$5$$$ — это $$$3, 5$$$, который не содержит $$$4$$$. Простой путь между $$$5$$$ и $$$7$$$ — $$$5, 3, 1, 2, 7$$$, который не содержит $$$6$$$. Простой путь между $$$6$$$ и $$$4$$$ — $$$6, 7, 2, 1, 3, 4$$$, который не содержит $$$5$$$. Таким образом, это дерево удовлетворяет всем ограничениям.

Вывод второго примера соответствует следующему дереву: