Migrated from Lutece 2531 w国的防御体系

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

$w$ 国位于 $s$ 大洲的腹心地带，在 $s$ 大洲上有许多国家，由于这些国家分散在 $w$ 国周围，恰好将 $w$ 国环绕起来，因此这些国家都对 $w$ 国打上了主意。而在这些对 $w$ 国虎视眈眈的国家中，最为迫切想要与 $w$ 国开战的国家要属 $f$ 国。$f$ 国历来狡猾，它深知贸然攻打 $w$ 国的风险，在其它国家没有行动的时候，它也会按兵不动。

不过在观望期间，$f$ 国会派出一名间谍前往 $w$ 国去视察敌方的兵力部署情况并得出一个大致的数值以表征 $w$ 国的实力。间谍 $L$ 在接受到 $f$ 国国王的任务后很快就来到了 $w$ 国，他前往了 $w$ 国的每个兵力据点，为每个兵力据点设置了一个编号（编号从 $1$ 开始），经过视察他发现任意两个兵力据点之间恰好只有一条路径将两者连通。除了记录兵力据点的位置关系外，间谍 $L$ 还记录了每个兵力据点内士兵的大致规模（后面简称为兵力规模），用一个整数来表征，记录完成后间谍 $L$ 就将这份数据带回了 $f$ 国。$f$ 国的一名高级官员 $G$ 看到了这份记录，他开始思考如何用一个整数来表征 $w$ 国的真实实力，他最开始想的是将所有兵力据点的士兵规模简单相加，但觉得这么做的话就没有考虑到兵力据点的位置关系，不能反映出真实的国家实力，因此他觉得需要找一条分布着兵力据点的路，用这条路的攻打难度来评估国家的真实实力。

由于每个兵力据点的兵力规模互不相同，因此为了方便起见，高级官员 $G$ 决定给所有的兵力据点按照兵力规模从小到大进行排名，并且排名从 $0$ 开始。高级官员 $G$ 设想对于一条路而言(一条路被定义为从一个兵力据点$a$到达兵力据点$b$所走的最短路径，其中$a$,$b$不相同)，这条路上分布的所有兵力据点中没有出现过的最小名次对应的兵力规模应该就是这条路的攻打难度，比如一条路径上有名次0 1 2 3 5对应的兵力据点，那么最小未出现名次就是4，那么这条路的攻打难度就是名次为 4 的兵力据点对应的兵力规模，特别地，如果最小未出现名次没有对应的兵力据点，我们认为这条路的攻打难度是无穷大。最后高级官员 $G$ 觉得所有路中攻打难度最高的一条路的攻打难度就是攻打 $w$ 国的难度。

在设定这样一套评价体系后，高级官员 $G$ 觉得他已经可以有效地掌握 $w$ 国的真实实力了，然而他不知道这套评价体系有着多么严重的缺陷，在若干年后攻打 $w$ 国的时候，$f$ 国差点亡国，这一切都归咎于这位高级官员 $G$ 对 $w$ 国实力错误的评价，不过这已经是后话了。

事实上当下 $f$ 国的人民和国王都对高级官员 $G$ 非常信任，他们将 $f$ 国的前程交给了高级官员 $G$，现在你，作为高级官员 $G$ 的一名助手，你需要帮他分析这份间谍 $L$ 搜集来的记录，并从中得出 $w$ 国的攻打难度是多少。不过在真正要攻打 $w$ 国之前，间谍 $L$ 还需要定期到 $w$ 国去视察兵力据点变动情况，奇怪的是间谍 $L$ 发现每次去视察都会有一个编号为 $a$ 的兵力据点的所有士兵迁移到另一个编号为 $b$ 的兵力据点，当然同一个兵力据点不能有太多的士兵，因此编号为 $b$ 的兵力据点的士兵也会迁移到编号为 $a$ 的兵力据点，于是这时候 $w$ 国的记录会被改变。

为了方便记录，间谍 $L$ 每次前往 $w$ 国视察后，都会用一个整数对 $(a,b)$ 表示 $w$ 国的兵力据点变动情况，即代表两个兵力据点的士兵发生了互换，相应地两个兵力据点的兵力规模也会发生互换。现在高级官员 $G$ 给你提出了更高的要求，那就是在每次记录变动之后仍然要计算出 $w$ 国的攻打难度，由于国王急切想要找到一个合适的时机攻打 $w$ 国，因此你需要非常快速地算出这个值。

一句话题意：

给定 $n$ 个节点的一棵树，节点 $i\ (1\le i\le n)$ 的权值为 $C_i$，节点权值互不相同。

记 $rk[i]$ 为节点 $i$ 权值在所有节点权值中的名次（名次从 $0$ 开始），记$D_i$为树上所有节点中第$i$小的权值($1\le i\le n$)，并且特别地，令 $D_{n+1}=+\infty$。

设节点 $u$ 到 $v$ 的最短路径为 $u,u_1,u_2,u_3\ldots ,v$，则路径 $u$ 到 $v$ 的权值 $w_{u,v}$ 被定义为 $w_{u,v}=D_{\text{mex}\{rk[u],rk[u_1],rk[u_2],\ldots ,rk[v]\}+1}$，其中 $\text{mex}\{a_1,a_2,a_3,\ldots ,a_n\}$ 被定义为 $a_1,a_2,\ldots ,a_n$ 中最小的未出现的非负整数，比如 $\text{mex}\{0,1,2,3,5\}=4, \text{mex}\{1,2,3\}=0$。

一棵树的权值 $W$ 被定义为其所有路径权值的最大值，也就是 $W=\max_{1\le u,v\le n,u\ne v}\{w_{u,v}\}$。

现在给定 $q$ 次操作，每次操作可以用一对数 $(a,b)$ 表示，代表交换 $a,b$ 两个节点的 $C$ 值，即 $\texttt{swap}(C_a,C_b)$。你需要在每次操作后输出此时整棵树的权值 $W$，注意当 $W=+\infty$ 的时候，输出 $-1$ 即可。

Input

在第一行给出两个整数 $n,q\ (2\le n\le 10^5 ,1\le q\le 10^5)$，代表 $w$ 国的 $n$ 个兵力据点（编号为 $1\sim n$）以及接下来会发生的$q$次兵力据点变动。

接下来一行给出 $n$ 个整数 $C_1,C_2,\ldots ,C_n\ (1\le C_i\le 10^9)$，从左到右依次代表编号 $1\sim n$ 的兵力据点的兵力规模。保证 $C_i$ 两两互不相同。

接下来 $n-1$ 行每行给出两个整数 $u,v\ (1\le u,v\le n,u\ne v)$，代表 $w$ 国的两个兵力据点 $u,v$ 之间有一条路，并且这条路上没有其它兵力据点。

接下来 $q$ 行每行给出两个整数 $a,b\ (1\le a,b\le n,a\ne b)$，代表一次兵力据点变动，具体含义在题面中已给出。

Output

在每次兵力据点变动后输出对应的 $w$ 国的攻打难度，注意如果攻打难度是无穷大则输出 $-1$ 即可。

Samples

3 1
3 5 7
1 2
1 3
1 2

-1

7 4
1 8 999999999 6 2 4 1000000000
1 2
1 5
2 3
2 4
5 6
5 7
1 5
3 4
2 4
5 7

999999999
999999999
8
4

Resources

2021 UESTC ICPC Training for Data Structures