output_description: Print the number of times Takahashi will hear his favorite sound.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      A B C
attempt: class Union_find(object):
      def __init__(self, N):
          # 親の番号を格納する。親だった場合は-(その集合のサイズ)
          self.parent = [-1] * (N)
  
      # Aがどのグループに属するか
      def root(self, A):
          if self.parent[A] < 0:
              return A
          else:
              # 親を繋ぎ変えて高速化
              self.parent[A] = self.root(self.parent[A])
              return self.parent[A]
  
      def size(self, A):
          return -self.parent[self.root(A)]
  
      # A,Bをくっつける
      def connect(self, A, B):
          # A,Bを直接つなぐのでなく、root(A),root(B)をつなぐ
          A = self.root(A)
          B = self.root(B)
          if A == B:
              return False
          # 大きい方に小さい方をくっつける
          if self.size(A) < self.size(B):
              A, B = B, A
          self.parent[A] += self.parent[B]
          self.parent[B] = A
          return True
  
  
  N, M = list(map(int, input().split()))
  A = []
  B = []
  for _ in range(M):
      a, b = list(map(int, input().split()))
      A.append(a - 1)
      B.append(b - 1)
  uni = Union_find(N)
  result = []
  unconv = int(N * (N - 1) / 2)
  for a, b in zip(reversed(A), reversed(B)):
      result.append(unconv)
      size_a = uni.size(a)
      size_b = uni.size(b)
      if uni.connect(a, b):
          unconv -= size_a * size_b
  for r in reversed(result):
      print(r)
  
problem_description: Statement
  
  Takahashi likes the sound when he buys a drink from a vending machine.
  
  That sound can be heard by spending A yen (the currency of Japan) each time.
  
  Takahashi has B yen. He will hear the sound as many times as he can with that
  money, but at most C times, as he would be satisfied at that time.
  
  How many times will he hear the sound?
samples: [{"input": "2 11 4", "output": "4\n    \n\nSince he has not less than 8 yen, he will hear the sound four times and be\nsatisfied.\n\n* * *"}, {"input": "3 9 5", "output": "3\n    \n\nHe may not be able to be satisfied.\n\n* * *"}, {"input": "100 1 10", "output": "0"}]