#4129. Haruna’s Breakfast

题目描述

Haruna每天都会给提督做早餐！ 这天她发现早饭的食材被调皮的 Shimakaze放到了一棵

树上，每个结点都有一样食材，Shimakaze要考验一下她。

每个食材都有一个美味度，Shimakaze会进行两种操作：

1、修改某个结点的食材的美味度。

2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。

请你帮帮Haruna吧。

输入格式

第一行包括两个整数n，m，代表树上的结点数(标号为1~n)和操作数。

第二行包括n个整数a1...an，代表每个结点的食材初始的美味度。

接下来n-1行，每行包括两个整数u，v，代表树上的一条边。

接下来m 行，每行包括三个整数

0 u x 代表将结点u的食材的美味度修改为 x。

1 u v 代表询问以u，v 为端点的链的mex值。

输出格式

对于每次询问，输出该链的mex值。

样例

样例输入

10 10  

1 0 1 0 2 4 4 0 1 0  

1 2  

2 3  

2 4  

2 5  

1 6  

6 7  

2 8  

3 9  

9 10  

0 7 14  

1 6 6  

0 4 9  

1 2 2  

1 1 8  

1 8 3  

0 10 9  

1 3 5  

0 10 0  

0 7 7

样例输出

0  

1  

2  

2  

3

数据范围与提示

1<=n<=5*10^4

1<=m<=5*10^4

0<=ai<=10^9