CF1508E.Tree Calendar

Yuu Koito and Touko Nanami are newlyweds! On the wedding day, Yuu gifted Touko a directed tree with $n$ nodes and rooted at $1$, and a labeling $a$ which is some DFS order of the tree. Every edge in this tree is directed away from the root.

After calling dfs(1) the following algorithm returns $a$ as a DFS order of a tree rooted at $1$ :

order := 0
a := array of length n

function dfs(u):
order := order + 1
a[u] := order
for all v such that there is a directed edge (u -> v):
dfs(v)

Note that there may be different DFS orders for a given tree.

Touko likes the present so much she decided to play with it! On each day following the wedding day, Touko performs this procedure once:

• Among all directed edges $u \rightarrow v$ such that $a_u \lt a_v$, select the edge $u' \rightarrow v'$ with the lexicographically smallest pair $(a_{u'}, a_{v'})$.
• Swap $a_{u'}$ and $a_{v'}$.

Days have passed since their wedding, and Touko has somehow forgotten which date the wedding was and what was the original labeling $a$! Fearing that Yuu might get angry, Touko decided to ask you to derive these two pieces of information using the current labeling.

Being her good friend, you need to find the number of days that have passed since the wedding, and the original labeling of the tree. However, there is a chance that Touko might have messed up her procedures, which result in the current labeling being impossible to obtain from some original labeling; in that case, please inform Touko as well.

柚子·小伊藤与远子·七海新婚了！在婚礼当天，柚子送给远子一棵有 $n$ 个节点、以节点 $1$ 为根的有向树，以及一个标记数组 $a$，该数组是这棵树的某种 DFS 序。树中每条边的方向均远离根节点。

执行 dfs(1) 后，以下算法将返回该树（以 $1$ 为根）的一个 DFS 序 $a$：

order := 0  
a := 长度为 n 的数组   
  
function dfs(u):  
 order := order + 1  
 a[u] := order  
 对所有满足存在有向边 (u -> v) 的 v：  
   dfs(v)  

注意：对于给定的树，可能存在多种不同的 DFS 序。

远子非常喜欢这份礼物，于是决定拿它来玩耍！自婚礼次日起，远子每天执行一次如下操作：

• 在所有满足 $a_u \lt a_v$ 的有向边 $u \rightarrow v$ 中，选出使序对 $(a_{u'}, a_{v'})$ 字典序最小的那条边 $u' \rightarrow v'$；
• 交换 $a_{u'}$ 和 $a_{v'}$。

距离婚礼已过去多日，远子却意外地忘记了婚礼的确切日期，也忘记了最初的标记数组 $a$！她担心柚子会生气，便请你根据当前的标记数组推断出这两个信息。

作为她的好友，你需要求出距婚礼已过去的天数，以及树最初的标记数组。然而，远子的操作过程有可能出错，导致当前的标记数组根本无法由任何初始标记数组经上述过程得到；此时，请一并告知远子这一情况。

The first line of the input contains an integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the number of nodes on the tree.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le n$, all $a_i$ are distinct) — the current labeling of the tree.

Each of the next $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u, v \le n$, $u \neq v$), describing an directed edge from $u_i$ to $v_i$. The edges form a directed tree rooted at $1$.

输入的第一行包含一个整数 $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$ 为根的有向树。

If the current labeling is impossible to arrive at from any DFS order, print NO.

Else, on the first line, print YES. On the second line, print a single integer denoting the number of days since the wedding. On the third line, print $n$ numbers space-separated denoting the original labeling of the tree.

If there are multiple correct outputs, print any. This means: you are allowed to output any pair (DFS order, number of days), such that we get the current configuration from the DFS order you provided in exactly the number of days you provided.

如果当前的标号无法通过任何 DFS 遍历顺序得到，则输出 NO。

否则，第一行输出 YES；第二行输出一个整数，表示自婚礼以来经过的天数；第三行输出 $n$ 个用空格分隔的数字，表示树的原始标号。

若存在多个正确答案，输出任意一个即可。也就是说：你可以输出任意一对（DFS 遍历顺序，天数），使得从你提供的 DFS 遍历顺序出发，恰好经过你提供的天数后，能得到当前的配置。

The following animation showcases the first sample test case. The white label inside the node represents the index of the node $i$, while the boxed orange label represents the value $a_i$.

以下动画展示了第一个样例测试用例。节点内部的白色标签表示节点的索引 $i$，而带框的橙色标签表示值 $a_i$。