In the depths of a mystical forest stands the "Luminous Tree", having N magical nodes. Each of these nodes possesses the unique capability to glow either in white or black. Initially, all nodes have a white glow.
The tree's structure is well-established, with node 1 serving as its root and (N−1) branches connecting the entirety of its nodes.
Travelers, having heard tales of the tree's peculiar characteristics, visit with specific queries. Their queries fall into two distinct categories:
In the First type of query, a traveler can specify a node and request its color to be changed. If the node is presently glowing white, it will be changed to black, and if it's black, it will be changed to white.
In the Second query type, a traveler can specify a node and ask a question about the tree's black-lit nodes. Specifically, they desire to know the maximum distance from their chosen node to any node glowing black in that node's subtree. If there is no black glowing node in the selected node's subtree, then the response for this query is −1.
As the guardian of the Luminous Tree, your mission is to efficiently address these traveler queries, particularly providing the answer for the second type of queries.
Input Format:
Output Format:
For each test case, address all the M queries. For each query of the second type, provide the answer in a new line. Print the answer for each query in a new line. If, for a second type query, there is no black glowing node in the selected node's subtree, then you need to print −1 as the answer for that query.
Constraints:
1≤T≤1053≤N≤1061≤u,v≤N1≤M≤106type∈[1,2]1≤x≤N The sum of all values of N over all test cases doesn't exceed 106The sum of all values of M over all test cases doesn't exceed 106
The first line denotes T = 1.
For test case 1:
We are given:
Now,