output_description: For each same operation, print 1 if x and y are in the same set, otherwise 0,
  in a line.
input_description: n q
      com1 x1 y1
      com2 x2 y2
      ...
      comq xq yq
      
  
  In the first line, n and q are given. Then, q queries are given where com
  represents the type of queries. '0' denotes unite and '1' denotes same
  operation.
attempt: import sys
  
  
  class UnionFind(object):
      def __init__(self):
          self.node_id = {}
          self.parent_id = []
          self.rank = []
  
      def find(self, node_id):
          while node_id != self.parent_id[node_id]:
              pp = self.parent_id[self.parent_id[node_id]]
              self.parent_id[node_id] = pp
              node_id = pp
          return node_id
  
      def add(self, x):
          if x in self.node_id:
              return self.node_id[x]
          node_id = len(self.node_id)
          self.node_id[x] = node_id
          self.parent_id.append(len(self.parent_id))
          self.rank.append(0)
          return node_id
  
      def union(self, p, q):
          i = self.find(p)
          j = self.find(q)
          if i == j:
              return
          if self.rank[i] < self.rank[j]:
              self.parent_id[i] = j
          elif self.rank[i] > self.rank[j]:
              self.parent_id[j] = i
          else:
              self.parent_id[j] = i
              self.rank[i] += 1
  
      def dump_groups(self):
          result = []
          group_id = {}
          for x, i in self.node_id.items():
              j = self.find(i)
              if j not in group_id:
                  group_id[j] = len(result)
                  result.append([])
              result[group_id[j]].append(x)
          return result
  
      def dump_dot(self):
          result = """digraph { graph [rankdir=LR];\n"""
          for i, target in enumerate(self.parent_id):
              result += """"%s" [label=\"%s\",shape=plaintext,shape=circle];\n""" % (i, i)
              if i != target:
                  result += """"%s" -> "%s";\n""" % (i, target)
          result += "}"
          return result
  
  
  uf = UnionFind()
  (n, q) = sys.stdin.readline().split()
  for i in range(int(n)):
      uf.add(i)
  for i in range(int(q)):
      (c, x, y) = sys.stdin.readline().split()
      if c == "0":
          uf.union(int(x), int(y))
      else:
          print(1 if uf.find(int(x)) == uf.find(int(y)) else 0)
  
problem_description: Disjoint Set
  
  Write a program which manipulates a disjoint set S = {S1, S2, . . . , Sk}.
  
  First of all, the program should read an integer n, then make a disjoint set
  where each element consists of 0, 1, ... n−1 respectively.
  
  Next, the program should read an integer q and manipulate the set for q
  queries. There are two kinds of queries for different operations:
  
    * unite(x, y): unites sets that contain x and y, say Sx and Sy, into a new set. 
    * same(x, y): determine whether x and y are in the same set.
samples: [{"input": "12\n    0 1 4\n    0 2 3\n    1 1 2\n    1 3 4\n    1 1 4\n    1 3 2\n    0 1 3\n    1 2 4\n    1 3 0\n    0 0 4\n    1 0 2\n    1 3 0", "output": "0\n    1\n    1\n    1\n    0\n    1\n    1"}]