You have directed acyclic forest. Every node except root nodes have 1 parent.

Query 1: Change parent of one node or make it a root node(it is guaranteed graph will not have cycle)

Query 2: input a node and output the root of the tree that node is in.

Number of nodes = 2e5 Number of queries = 2e5