This is the Hard Version of the problem. The only difference between the two versions is that in the Hard Version the tree may be of any shape. This problem is interactive. Baudelaire is very rich, so he bought a tree of size (n), rooted at some arbitrary node. Additionally, every node has a value of (1) or (-1). Cow the Nerd saw the tree and fell in love with it. However, computer science doesn't pay him enough, so he can't afford to buy it. Baudelaire decided to play a game with Cow the Nerd, and if he won, he would gift him the tree. Cow the Nerd does not know which node is the root, and he doesn't know the values of the nodes either. However, he can ask Baudelaire queries of two types: (1) (k) (u_1) (u_2) (...) (u_k): Let (f(u)) be the sum of the values of all nodes in the path from the root of the tree to node (u). Cow the Nerd may choose an integer (k) ((1 \le k \le n)) and (k) nodes (u_1, u_2, ..., u_k), and he will receive the value (f(u_1) + f(u_2) + ... + f(u_k)). (2) (u): Baudelaire will toggle the value of node (u). Specifically, if the value of (u) is (1), it will become (-1), and vice versa. Cow the Nerd wins if he guesses the value of every node correctly (the values of the final tree, after performing the queries) within (n + 200) total queries. Can you help him win? The first line of the input contains a single integer (t) ((1 \le t \le 100)), the number of test cases. The first line of each test case contains a single integer (n) ((2 \le n \le 10^3)), the size of the tree. Each of the next (n-1) lines contains two integers (u) and (v) ((1 \le u, v \le n, u \neq v)), denoting an edge between nodes (u) and (v) in the tree. It is guaranteed that the sum of (n) over all test cases does not exceed (10^3) and that each graph provided is a valid tree. To ask a query of type (1), output a line in the foll