output_description: Print the number of the possible pairs of integers u and v, modulo 10^9+7.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N
attempt: class UnionFind:
      def __init__(self, n):
          self.par = [i for i in range(n + 1)]
          self.rank = [0] * (n + 1)
  
      # 検索
      def find(self, x):
          if self.par[x] == x:
              return x
          else:
              self.par[x] = self.find(self.par[x])
              return self.par[x]
  
      # 併合
      def unite(self, x, y):
          x = self.find(x)
          y = self.find(y)
          if self.rank[x] < self.rank[y]:
              self.par[x] = y
          else:
              self.par[y] = x
              if self.rank[x] == self.rank[y]:
                  self.rank[x] += 1
  
      # 同じ集合に属するか判定
      def same_check(self, x, y):
          return self.find(x) == self.find(y)
  
  
  N, K, L = map(int, input().split())
  mark = 0
  U1 = UnionFind(N)
  U2 = UnionFind(N)
  for i in range(K):
      p, q = map(int, input().split())
      U1.unite(p - 1, q - 1)
  for i in range(L):
      r, s = map(int, input().split())
      U2.unite(r - 1, s - 1)
  List = []
  for i in range(N):
      List.append((U1.par[i], U2.par[i], i))
  List = sorted(List)
  cnt = 0
  member = []
  ans = [0] * N
  for i in range(N - 1):
      if List[i][0] == List[i + 1][0] and List[i][1] == List[i + 1][1]:
          cnt += 1
          if member:
              member.append(List[i + 1][2])
          else:
              member.append(List[i][2])
              member.append(List[i + 1][2])
      else:
          for j in member:
              ans[j] = cnt
          cnt = 0
          member = []
  for j in member:
      ans[j] = cnt
  for i in range(N):
      print(ans[i] + 1)
  
problem_description: Statement
  
  You are given a positive integer N. Find the number of the pairs of integers u
  and v (0≦u,v≦N) such that there exist two non-negative integers a and b
  satisfying a xor b=u and a+b=v. Here, xor denotes the bitwise exclusive OR.
  Since it can be extremely large, compute the answer modulo 10^9+7.
samples: [{"input": "3", "output": "5\n    \n\nThe five possible pairs of u and v are:\n\n  * u=0,v=0 (Let a=0,b=0, then 0 xor 0=0, 0+0=0.)\n\n  * u=0,v=2 (Let a=1,b=1, then 1 xor 1=0, 1+1=2.\uff09\n\n  * u=1,v=1 (Let a=1,b=0, then 1 xor 0=1, 1+0=1.\uff09\n\n  * u=2,v=2 (Let a=2,b=0, then 2 xor 0=2, 2+0=2.\uff09\n\n  * u=3,v=3 (Let a=3,b=0, then 3 xor 0=3, 3+0=3.\uff09\n\n* * *"}, {"input": "1422", "output": "52277\n    \n\n* * *"}, {"input": "1000000000000000000", "output": "787014179"}]