output_description: Print the number of possible values of S - T.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N X D
attempt: #!/usr/bin/env python3
  # 写経
  import sys
  
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  
  # 　縦に並んだ入力を受け取りたい時はread().split()をとる zip(m,m)で分ける
  N, U, V = map(int, readline().split())
  m = map(int, read().split())
  AB = zip(m, m)
  
  # tree の受け取り：頂点の数＋１のリストを用意して、それぞれの頂点が辺を貼るnodeを全てリストに保存
  graph = [[] for _ in range(N + 1)]
  for a, b in AB:
      graph[a].append(b)
      graph[b].append(a)
  
  
  # 全探索して入力頂点からの距離を返す
  # 全ての頂点に対して、
  def dfs(v):
      dist = [-1] * (N + 1)
      stack = [v]
      dist[v] = 0
      while stack:
          v = stack.pop()
          dw = dist[v] + 1
          for w in graph[v]:  # 頂点から辺が貼られている頂点に対して
              if dist[w] >= 0:  # すでに訪れている
                  continue
              dist[w] = dw  # 訪れてないなら更新
              stack.append(w)
      return dist
  
  
  DU, DV = dfs(U), dfs(V)
  
  answer = 0
  # 元の場所以外の全ての頂点を探索する
  for u, v in zip(DU[1:], DV[1:]):
      if u < v:  # 逃げる方が先につく中で最短を探す
          x = v - 1
          if answer < x:
              answer = x
  
  print(answer)
  
problem_description: Statement
  
  We have an integer sequence A of length N, where A_1 = X, A_{i+1} = A_i + D (1
  \leq i < N ) holds.
  
  Takahashi will take some (possibly all or none) of the elements in this
  sequence, and Aoki will take all of the others.
  
  Let S and T be the sum of the numbers taken by Takahashi and Aoki,
  respectively. How many possible values of S - T are there?
samples: [{"input": "3 4 2", "output": "8\n    \n\nA is (4, 6, 8).\n\nThere are eight ways for (Takahashi, Aoki) to take the elements: ((), (4, 6,\n8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8),\n(6))), ((6, 8), (4))), and ((4, 6, 8), ()).\n\nThe values of S - T in these ways are -18, -10, -6, -2, 2, 6, 10, and 18,\nrespectively, so there are eight possible values of S - T.\n\n* * *"}, {"input": "2 3 -3", "output": "2\n    \n\nA is (3, 0). There are two possible values of S - T: -3 and 3.\n\n* * *"}, {"input": "100 14 20", "output": "49805"}]