CF1083C Max Mex

Once Grisha found a tree (connected graph without cycles) with a root in node $ 1 $ . But this tree was not just a tree. A permutation $ p $ of integers from $ 0 $ to $ n - 1 $ is written in nodes, a number $ p_i $ is written in node $ i $ . As Grisha likes to invent some strange and interesting problems for himself, but not always can solve them, you need to help him deal with two types of queries on this tree. Let's define a function $ MEX(S) $ , where $ S $ is a set of non-negative integers, as a smallest non-negative integer that is not included in this set. Let $ l $ be a simple path in this tree. So let's define indices of nodes which lie on $ l $ as $ u_1 $ , $ u_2 $ , $ \ldots $ , $ u_k $ . Define $ V(l) $ as a set { $ p_{u_1} $ , $ p_{u_2} $ , $ \ldots $ , $ p_{u_k} $ }. Then queries are: 1. For two nodes $ i $ and $ j $ , swap $ p_i $ and $ p_j $ . 2. Find the maximum value of $ MEX(V(l)) $ in all possible $ l $ .

N/A

N/A

Number written in brackets is a permutation value of a node.  In the first example, for the first query, optimal path is a path from node $ 1 $ to node $ 5 $ . For it, set of values is $ \{0, 1, 2\} $ and $ MEX $ is $ 3 $ .  For the third query, optimal path is a path from node $ 5 $ to node $ 6 $ . For it, set of values is $ \{0, 1, 4\} $ and $ MEX $ is $ 2 $ .  In the second example, for the first query, optimal path is a path from node $ 2 $ to node $ 6 $ . For it, set of values is $ \{0, 1, 2, 5\} $ and $ MEX $ is $ 3 $ .  For the third query, optimal path is a path from node $ 5 $ to node $ 6 $ . For it, set of values is $ \{0, 1, 3\} $ and $ MEX $ is $ 2 $ .  For the fifth query, optimal path is a path from node $ 5 $ to node $ 2 $ . For it, set of values is $ \{0, 1, 2, 3\} $ and $ MEX $ is $ 4 $ .  For the seventh query, optimal path is a path from node $ 5 $ to node $ 4 $ . For it, set of values is $ \{0, 1, 2, 3\} $ and $ MEX $ is $ 4 $ .  For the ninth query, optimal path is a path from node $ 6 $ to node $ 5 $ . For it, set of values is $ \{0, 1, 3\} $ and $ MEX $ is $ 2 $ .