output_description: For each diff question, print the difference between $a_x$ and $a_y$ $(a_y -
  a_x)$.
input_description: $n \; q$
      $query_1$
      $query_2$
      :
      $query_q$
      
  
  In the first line, $n$ and $q$ are given. Then, $q$ information/questions are
  given in the following format.
  
      
      
      0 $x \; y\; z$
      
  
  or
  
      
      
      1 $x \; y$
      
  
  where '0' of the first digit denotes the relate information and '1' denotes
  the diff question.
attempt: #!/usr/bin/env python3
  # DSL_1_B: Weighted Union Find Trees
  
  
  class WeightedUnionFind:
      def __init__(self, n):
          self.n = n
          self.nodes = [i for i in range(n)]
          self.weights = [0 for _ in range(n)]
          self.size = [1 for _ in range(n)]
  
      def connected(self, i, j):
          wi, ri = self.root(i)
          wj, rj = self.root(j)
          return ri == rj
  
      def union(self, i, j, w):
          wi, ri = self.root(i)
          wj, rj = self.root(j)
          if ri == rj:
              return
  
          if self.size[ri] < self.size[rj]:
              self.nodes[ri] = rj
              self.weights[ri] = wj - wi + w
              self.size[rj] += self.size[ri]
          else:
              self.nodes[rj] = ri
              self.weights[rj] = wi - wj - w
              self.size[ri] += self.size[rj]
  
      def weight(self, i, j):
          wi, ri = self.root(i)
          wj, rj = self.root(j)
          if ri != rj:
              raise ValueError("{} and {} is not connected".format(i, j))
  
          return wi - wj
  
      def root(self, i):
          r = self.nodes[i]
          w = self.weights[i]
          while r != self.nodes[r]:
              w += self.weights[r]
              r = self.nodes[r]
          return w, r
  
  
  def run():
      n, q = [int(i) for i in input().split()]
      wuf = WeightedUnionFind(n)
  
      for _ in range(q):
          com, *args = input().split()
          if com == "0":
              wuf.union(*[int(i) for i in args])
          elif com == "1":
              x, y = [int(i) for i in args]
              if wuf.connected(x, y):
                  print(wuf.weight(x, y))
              else:
                  print("?")
  
  
  if __name__ == "__main__":
      run()
  
problem_description: Weighted Union Find Trees
  
  There is a sequence $A = a_0, a_1, ..., a_{n-1}$. You are given the following
  information and questions.
  
    * relate$(x, y, z)$: $a_y$ is greater than $a_x$ by $z$
    * diff$(x, y)$: report the difference between $a_x$ and $a_y$ $(a_y - a_x)$
samples: [{"input": "6\n    0 0 2 5\n    0 1 2 3\n    1 0 1\n    1 1 3\n    0 1 4 8\n    1 0 4", "output": "?\n    10"}]