Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem.
You are given a tree with nodes and each node's value is initially . The problem asks you to operate the following two types of queries:
- "1 u x" assign to the value of the node .
- "2 u v" print the maximum value of the nodes on the unique path between and .
Input Format
First line consists of two integers seperated by a space: and .
Following lines consisting of two integers denotes the undirectional edges of the tree.
Following lines consist of the queries you are asked to operate.
Constraints
It is guaranteed that input denotes a connected tree with nodes. Nodes are enumerated with 0-based indexing.
Output Format
For each second type of query print single integer in a single line, denoting the asked maximum value.
Sample Input
3 3
0 1
1 2
1 0 1
1 1 2
2 0 2
Sample Output
2
Explanation
After the first two updates value of the th node is and st node is . That is why maxiumum value on the path between and is .