E. Дерево-календарь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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.

Входные данные

В первой строке входных данных содержится целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — количество вершин в дереве.

Во второй строке содержатся $$$n$$$ целые числа $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le n$$$, все $$$a_i$$$ различны) — текущая маркировка дерева.

Каждая из следующих $$$n - 1$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), описывающие ориентированное ребро от $$$u_i$$$ до $$$v_i$$$. Ребра образуют корневое ориентированное дерево с корнем в $$$1$$$.

Выходные данные

Если текущую маркировку невозможно получить ни из какого DFS-обхода, выведите NO.

В противном случае в первой строке выведите YES. Во второй строке выведите единственное целое число, обозначающее количество дней со дня свадьбы. В третьей строке выведите $$$n$$$ чисел через пробел, обозначающих оригинальную маркировку дерева.

Если есть несколько правильных решений, вы можете вывести любое. Это означает, что вы можете вывести любую пару (DFS-обход, количество дней), для которой мы получим текущую конфигурацию, начав из DFS-обхода, который вы предоставили, ровно через предоставленное вами количество дней.

Примеры
Входные данные
7
4 5 2 1 7 6 3
1 5
7 6
1 2
2 7
3 4
1 3
Выходные данные
YES
5
1 4 2 3 7 6 5
Входные данные
7
7 6 5 3 1 4 2
4 3
2 5
3 7
1 4
7 2
2 6
Выходные данные
NO
Примечание

Следующая анимация демонстрирует первый пример. Белая метка внутри вершины обозначает номер вершины $$$i$$$, а оранжевая метка — значение $$$a_i$$$.