U142788 【1123T1】ZZH的游戏

Alice 和 Bob 各自在一棵树上，每棵树都有 $n$ 个点。Alice 初始在 $s$，Bob初始在 $t$。 两人轮流走：轮到自己时，可以选择不动，或者移动一条边走到相邻结点上。 当2人都到 $1$ 时，游戏结束。游戏的分数是所有时刻中，两人所在的点编号的和的最大值。 Alice 和 Bob 会合作让游戏结束时的分数尽量小。两人都极其聪明，因此两人都会采用最优策略。 请你求出最小分数。

第一行一个非负整数 $T$，代表有 $T$ 组数据。 每组数据第一行1个正整数 $n$，表示2棵树的点数。 然后 $n-1$ 行，每行两个正整数 $(u,v)$，表示 Alice 树上的一条边 。 然后 $n-1$ 行，每行两个正整数 $(u,v)$，表示 Bob 树上的一条边 。 然后一行两个正整数 $s,t$，分别表示初始位置。

输出 $T$ 行，每行1个整数代表最小分数。

首先 Alice 移动到 4，接下来 Bob 不动。 然后 Alice 移动到 2，接下来 Bob 移动到 4。 然后 Alice 不动，Bob 移动到 5。 然后 Alice 不动，Bob 移动到 1。 接下来 Alice 移动至 1 即可。 对于所有数据，保证 $\sum n\le 10^6, T\le 10^4$。 对于测试点1，$T=0$ 对于测试点2-4，$\sum n\le 100$ 对于测试点5-8，$\sum n\le 1000$ 对于测试点9-12，$\sum n\le 200000$，两棵树均为随机生成 对于测试点13-17，$\sum n\le 200000$ 对于测试点18-20，无特殊限制