В компании Dogeforces работают \(k\) сотрудников. У каждого сотрудника, кроме сотрудников нижнего звена, есть не менее \(2\) подчиненных. У сотрудников нижнего звена нет подчиненных. У каждого сотрудника (кроме руководителя компании) есть ровно один непосредственный начальник. Руководитель компании является непосредственным или косвенным начальником всех сотрудников. Известно, что в Dogeforces любой начальник получает зарплату строго больше, чем все его подчиненные.
Полная структура компании является секретом, но вам известно количество сотрудников нижнего звена и для каждой пары сотрудников нижнего звена известна зарплата их общего начальника (если таких начальников несколько, то начальника с минимальной зарплатой). Вам предстоит восстановить структуру компании.
Выходные данные
В первую строку выведите одно целое число \(k\) — количество сотрудников в компании.
Во второй строке выведите \(k\) целых чисел \(c_1, c_2, \dots, c_k\), где \(c_i\) — зарплата сотрудника с номером \(i\).
В третьей строке выведите одно целое число \(r\) — номер сотрудника, который является руководителем компании.
В последующих \(k-1\) строках выведите по два целых числа \(v\) и \(u\) (\(1 \le v, u \le k\)) — номер сотрудника и его непосредственного начальника.
Обратите внимание, что сотрудники нижнего звена имею номера с \(1\) по \(n\), а для остальных сотрудников вам предстоит назначить номера от \(n+1\) до \(k\). Если корректных структур компании несколько, вы можете вывести любую из них.
Примечание
Одна из возможных структур в первом примере: 
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 5 7
5 1 7
7 7 4
|
5
2 1 4 7 5
4
1 5
2 5
5 4
3 4
|