题目描述

自古以来，伯兰德由善良公正的国王统治，王位世袭。但艰难时代到来了，命运使王朝中断，国家陷入混乱。一些城市被互相敌对的匪帮占领，另一些城市则完全没有统治者。

起初，一些城市中出现了犯罪帮派，并且每个帮派最初恰好控制一个城市。每个帮派都把自己最初诞生的城市选为首都。之后每一年，恰好一个帮派决定扩张领地，攻占某个此前无人统治或已被其他帮派统治的城市。

为了占领目标城市，该帮派的武装队伍从自己的首都出发，沿途攻占到目标城市路径上的所有城市。所有帮派首都都防守极严，不能通过，更不用说攻占。因此，进攻帮派首都到目标城市的路径上不能经过其他帮派的首都。

历史上，伯兰德有 $N$ 个城市和 $N-1$ 条双向道路，任意两个城市之间都能互相到达，即道路构成一棵树。

多年后，旧日档案已经遗失。现在你得到了一张当时的伯兰德地图。地图上标出了每个帮派的首都，并且对每个城市标注了在某一时刻它属于哪个帮派（到那时已经没有自由城市）。

请判断是否存在某种攻占序列可以产生地图所示的控制关系。如果存在，请输出一种长度不超过 $N$ 的攻占序列；否则输出地图有误。

输入格式

第一行包含两个整数 $N,M$，表示城市数和犯罪帮派数。

接下来 $N-1$ 行，每行包含两个不同整数 $a_i,b_i$，表示城市 $a_i$ 与 $b_i$ 之间有一条双向道路。

下一行包含 $M$ 个互不相同的整数 $c_i$，表示地图上第 $i$ 个帮派的首都位于城市 $c_i$。

最后一行包含 $N$ 个整数 $d_i$，表示城市 $i$ 在地图上属于编号为 $d_i$ 的帮派。保证对所有 $i$，有 $d_{c_i}=i$。

输出格式

如果存在这样的攻占序列，第一行输出 YES。

第二行输出一个整数 $S$，表示你找到的攻占序列长度，要求 $0 \le S \le N$。

接下来 $S$ 行，每行输出两个不同整数 $x_i,y_i$，表示第 $i$ 年由首都为 $x_i$ 的帮派发起进攻，目标城市为 $y_i$。

如果地图有误，无法由上述规则得到，则输出一行 NO。

保证如果存在可行攻占序列，则一定存在长度不超过 $N$ 的序列。

为了方便参赛者，检查程序不要求在攻占城市 $y_i$ 时，它一定不属于城市 $x_i$ 所属帮派。甚至允许输出路径上所有城市本来就属于同一帮派的攻占操作。但除此之外，所有攻占操作的要求必须满足。

数据范围

$1 \le M \le N \le 300000$。

样例

样例 1

4 2
1 3
2 3
3 4
1 2
1 2 2 1

YES
2
1 4
2 3

样例 2

5 3
1 3
2 3
3 4
3 5
1 2 3
1 2 3 1 3

NO

样例解释

第一个样例中，一种可能的历史过程如下：

• 初始时，城市 1 和 2 中分别形成一个帮派，城市 3 和 4 尚无归属；
• 第一年，第一个帮派出发攻占城市 4，途中控制城市 3；
• 第二年，第二个帮派从第一个帮派手中夺取城市 3。

第二个样例中不存在能得到该地图的攻占序列。

评分说明