Задача . E. Дерево-календарь

Yuu Koito и Touko Nanami — молодожёны! В день свадьбы Yuu подарила Touko ориентированное дерево с \(n\) вершинами и корнем в \(1\), а также маркировку \(a\), которая является некоторым DFS обходом дерева. Каждое ребро в этом дереве направлено в сторону от корня.

Следующий алгоритм после вызова dfs(1) возвращает \(a\) — DFS-обход дерева, корнем которого является \(1\):

номер := 0
a := массив длины n

функция dfs(u):
    номер := номер + 1
    a[u] := номер
    для всех v, для которых есть ориентированное ребро (u -> v):
        dfs(v)

Обратите внимание, что для дерева может существовать несколько различных DFS-обходов

Touko настолько понравился подарок, что она решила поиграть с ним! Каждый день, начиная с дня после свадьбы, Touko выполняет следующую процедуру один раз:

• Среди всех ориентированных рёбер \(u \rightarrow v\) таких, что \(a_u < a_v\), выберите рёбро \(u' \rightarrow v'\) с лексикографически минимальной парой \((a_{u'}, a_{v'})\).
• Обменяйте местами \(a_{u'}\) и \(a_{v'}\).

Прошли дни со свадьбы, а Touko как-то забыла, когда была свадьба, и какой была оригинальная маркировка \(a\)! Опасаясь, что Yuu может разозлиться, Touko решила попросить вас определить эту информацию, используя текущую маркировку.

Будучи ее хорошим другом, вы должны найти количество дней, прошедших со свадьбы, и оригинальную маркировку дерева. Однако есть шанс, что Touko могла ошибиться в процессе, в результате чего текущую маркировку невозможно получить ни из какой начальной маркировки, в этом случае, пожалуйста, сообщите об этом Touko.