Деревом размера n называется неориентированный связный граф из n вершин без циклов.
Рассмотрим некоторое дерево из n вершин. Назовем дерево инвариантным относительно перестановки p = p1p2... pn, если для любых двух вершин дерева u и v выполняется утверждение: «Вершины u и v соединены ребром тогда и только тогда, когда вершины pu и pv соединены ребром».
Вам дана перестановка p размера n. Найдите какое-нибудь дерево размера n, инвариантное относительно данной перестановки.
Выходные данные
Если искомого дерева не существует, то выведите «NO» (без кавычек).
Иначе выведите «YES», а затем выведите n - 1 строку, в каждой из которых находится по два целых числа — концы очередного ребра искомого дерева. Вершины нумеруются с единицы, порядок следования рёбер и порядок следования вершин внутри ребра не имеет значения.
Если решений несколько, выведите любое из них.
Примечание
В первом тесте из условия, при применении к ребру перестановки, ребро (4, 1) перейдет в ребро (1, 4), ребро (4, 2) перейдет в ребро (1, 3), а ребро (1, 3) перейдет в ребро (4, 2). Все эти ребра есть в ответе.
Можно заметить, что во втором тесте из условия, ни одно дерево не подходит под ограничения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 3 2 1
|
YES
4 1
4 2
1 3
|
|
2
|
3
3 1 2
|
NO
|