小糸优和七海冬子结婚了!婚礼当天,Yuu 送给 Touko 一棵有向树,其中有 $$$n$$$ 节点,根为 $$$1$$$,标签 $$$a$$$ 是树的某种 DFS 顺序。这棵树中的每条边都远离根。
调用 dfs(1) 后,以下算法返回 $$$a$$$ 作为以 $$$1$$$ 为根的树的 DFS 顺序:
请注意,给定的树可能有不同的 DFS 顺序。
灯子非常喜欢这个礼物,她决定玩它!婚礼后的每一天,Touko 都会执行一次此程序:
- 在所有有向边 $$$u \rightarrow v$$$ 中,使得 $$$a_u < a_v$$$,选择具有字典顺序最小对 $$$(a_{u'}, a_{v'})$$$ 的边 $$$u' \rightarrow v'$$$。
- 交换 $$$a_{u'}$$$ 和 $$$a_{v'}$$$。
他们的婚礼已经过去了很多天,Touko 不知何故忘记了婚礼的日期以及原来的标签 $$$a$$$ 是什么!由于担心悠会生气,灯子决定让你用现在的标签推导出这两条信息。
作为她的好朋友,你需要找到婚礼后已经过去的天数,以及树的原始标签。不过,有可能是灯子搞砸了程序,导致现在的标签无法从某些原始标签中获得;这种情况下,也请通知桐子。
输入
输入的第一行包含一个整数 $$$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 订单中获取当前配置。
示例
输入 #1
7 4 5 2 1 7 6 3 1 5 7 6 1 2 2 7 3 4 1 3
输出 #1
YES 5 1 4 2 3 7 6 5
输入 #2
7 7 6 5 3 1 4 2 4 3 2 5 3 7 1 4 7 2 2 6
输出 #2
NO
注意
以下动画展示了第一个示例测试用例。节点内的白色标签代表节点$$$i$$$的索引,而方框内的橙色标签代表值$$$a_i$$$。