У Родокса есть дерево из \(n\) вершин, но он не помнит его структуру. Вершины дерева пронумерованы от \(1\) до \(n\).
Отрезок \([l,r]\) (\(1 \leq l \leq r \leq n\)) называется хорошим, если вершины \(l\), \(l + 1\), ..., \(r\) образуют связную компоненту в дереве Родокса. Иначе отрезок называется плохим.
Например, для дерева на рисунке ниже только отрезок \([3,4]\) является плохим, а все остальные отрезки хорошие.
Для каждого из \(\frac{n(n+1)}{2}\) отрезков Родокс помнит, хорошим является этот отрезок, или плохим. Можете помочь ему восстановить дерево? Если существуют несколько решений, выведите любое из них.
Гарантируется, что существует хотя бы одно дерево, подходящее под описание Родокса.
Выходные данные
Для каждого набора входных данных выведите \(n-1\) строку, описывающую ваше дерево.
В \(i\)-й из этих строк выведите два целых числа \(u_i\) и \(v_i\) (\(1 \leq u_i,v_i \leq n\)), означающие, что в дереве есть ребро между вершинами \(u_i\) и \(v_i\).
Если существуют несколько решений, выведите любое из них.
Примечание
Первый пример объяснен в условии.
Во втором примере одно из возможных деревьев следующее:
В третьем примере одно из возможных деревьев следующее:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
1111
111
10
1
6
111111
11111
1111
111
11
1
12
100100000001
11100000001
1000000000
100000000
10010001
1110000
100000
10000
1001
111
10
1
|
1 2
2 3
2 4
1 2
2 3
3 4
4 5
5 6
2 3
6 7
10 11
2 4
6 8
10 12
1 4
5 8
9 12
5 12
2 12
|