CF1930H Interactive Mex Tree

This is an interactive problem. Alice has a tree $ T $ consisting of $ n $ nodes, numbered from $ 1 $ to $ n $ . Alice will show $ T $ to Bob. After observing $ T $ , Bob needs to tell Alice two permutations $ p_1 $ and $ p_2 $ of $ [1, 2, \ldots, n] $ . Then, Alice will play $ q $ rounds of the following game. - Alice will create an array $ a $ that is a permutation of $ [0,1,\ldots,n-1] $ . The value of node $ v $ will be $ a_v $ . - Alice will choose two nodes $ u $ and $ v $ ( $ 1 \leq u, v \leq n $ , $ u \neq v $ ) of $ T $ and tell them to Bob. Bob will need to find the $ \operatorname{MEX}^\dagger $ of the values on the unique simple path between nodes $ u $ and $ v $ . - To find this value, Bob can ask Alice at most $ 5 $ queries. In each query, Bob should give three integers $ t $ , $ l $ and $ r $ to Alice such that $ t $ is either $ 1 $ or $ 2 $ , and $ 1 \leq l \leq r \leq n $ . Alice will then tell Bob the value equal to $ $$$\min_{i=l}^{r} a[p_{t,i}]. $ $

Note that all rounds are independent of each other. In particular, the values of $ a $ , $ u $ and $ v $ can be different in different rounds.

Bob is puzzled as he only knows the HLD solution, which requires $ O(\\log(n)) $ queries per round. So he needs your help to win the game.

$ ^\\dagger $ The $ \\operatorname{MEX} $ (minimum excludant) of a collection of integers $ c\_1, c\_2, \\ldots, c\_k $ is defined as the smallest non-negative integer $ x $ which does not occur in the collection $ c$$$.

N/A

N/A

In the first test, the interaction proceeds as follows. SolutionJuryExplanation1There are 1 test cases.3 1The tree $ T $ consists of $ 3 $ nodes, and Alice will play for only one round.1 2First edge of $ T $ 2 3Second edge of $ T $ 1 2 3The permutation $ p_1 $ 2 1 3The permutation $ p_2 $ Alice shuffles $ a $ to $ a=[0,2,1] $ before giving the nodes for the only round.2 3Nodes for the round? 1 2 31 $ \min(a_{p_{1,2}},a_{p_{1,3}})=\min(a_2,a_3)=1 $ ? 2 1 30 $ \min(a_{p_{2,1}},a_{p_{2,2}},a_{p_{2,3}})=\min(a_2,a_1,a_3)=0 $ ! 01Considering the output of queries, it is clear that $ \operatorname{MEX} $ is $ 0 $ . Since the output is correct, the jury responds with $ 1 $ .After each test case, make sure to read $ 1 $ or $ -1 $ .