Alice and Bob play a game. The game starts with a graph that contains nodes and no edges. You are required to process queries of two types:
Input format
Nodes and for queries of the first type and node for queries of the second type are generated as follows:
where denotes the answer for the last query of the second type (initially )
Output format
For each query of type 2, print one integer denoting the answer to the query.
generated Queries:
2 1 where node 1 is reachable
2 2 where node 2 is not reachable
1 1 2 add edge from 1 to 2
2 2 where node 2 is reachable
1 3 4 add edge from 3 to 4
1 3 4 add edge from 3 to 4
2 4 where node 4 is not reachable
1 2 3 add edge from 2 to 3
2 4 where node 4 is reachable