Лорд Омкар хотел бы, чтобы у него было дерево с \(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\).
Сможете ли вы помочь Лорду Омкару и стать его самым доверенным учеником? Вам нужно будет найти божественные деревья для нескольких наборов ограничений. Можно показать, что при ограничениях задачи божественное дерево всегда найдется.
Выходные данные
Для каждого набора входных данных выведите \(n-1\) строку, обозначающих \(n-1\) ребро в дереве. В каждой строке выведите два целых числа \(u\) и \(v\) (\(1 \le u, v \le n\), \(u \neq v\)), обозначающие, что между вершинами \(u\) и \(v\) есть ребро. Данные ребра должны образовывать дерево, удовлетворяющее ограничениям Омкара.
Примечание
Вывод первого набора входных данных соответствует следующему дереву:
Для первого ограничения, простой путь между
\(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\). Таким образом, это дерево удовлетворяет всем ограничениям.
Вывод второго примера соответствует следующему дереву:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|