output_description: Print the answer.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      a_1 b_1
      \vdots
      a_{N-1} b_{N-1}
attempt: BASE = 9973
  MOD1 = 10**9 + 7
  MOD2 = 998244353
  
  
  class RollingHash:
      # 文字列Sのローリングハッシュを構築
      # 計算量: O(N)
      def __init__(self, S, MOD):
          self.MOD = MOD
          # acc[i]はS[0:i]のハッシュ値となる
          self.acc = [0]
          a = 0
          # 累積和を計算するイメージ
          for i, c in enumerate(S):
              h = ord(c) - ord("a") + 1
              offset = pow(BASE, i, MOD)
              a = (a + (h * offset)) % MOD
              self.acc.append(a)
  
      # S[i:j]のハッシュ値を返す
      # 計算量: O(1)
      def hash(self, i, j):
          # 累積和を用いて部分区間の和を計算するイメージ
          # 注意: 基数によるオフセットをキャンセルする必要がある
          offset = pow(BASE, i, self.MOD)
          # 素数MODを法とする剰余類における除算は逆元を乗算することで計算できる
          # 素数MODを法とする剰余類におけるxの逆元はx^(MOD - 2)に等しい
          offset_inv = pow(offset, self.MOD - 2, self.MOD)
          return ((self.acc[j] - self.acc[i]) * offset_inv) % self.MOD
  
  
  N = int(input())
  S = input()
  
  # Sのローリングハッシュを計算しておく
  rolling1 = RollingHash(S, MOD1)
  rolling2 = RollingHash(S, MOD2)
  
  # 長さmのダジャレがSに含まれるならば、長さm-1のダジャレも含まれる
  # つまり、長さmのダジャレがSに含まれるならば真となる述語をP(m)とすると、以下を満たす整数cが存在する:
  #   - 0以上c以下の整数mについてP(m)は真
  #   - cより大きい整数mについてP(m)は偽
  # ※ Pは単調関数ということ
  # このcを二分探索で発見すれば高速化できる！
  
  # P(ok)は真
  ok = 0
  # P(ng)は偽
  ng = N
  while ng - ok > 1:
      # 区間[ok, ng)の中央値をmとする
      m = (ok + ng) // 2
  
      # 長さmのダジャレが存在するか判定する
      # 長さmのformerのハッシュ値のキャッシュ
      former_cache1 = set()
      former_cache2 = set()
      p = False
      # latterに着目してループを回す
      for i in range(m, N):
          # ダジャレ長を決め打ちしているのでjを直接計算できる
          j = i + m
          # S[i:j]がSをはみ出したらループ終了
          if j > N:
              break
          # formerのハッシュ値をキャッシュする
          former_cache1.add(rolling1.hash(i - m, i))
          former_cache2.add(rolling2.hash(i - m, i))
          # キャッシャに同一のハッシュ値が存在する場合（ハッシュ値が衝突した場合）、ダジャレになっていると判定できる
          # ハッシュ値の計算、キャッシュ存在判定は共にO(1)で処理できる！
          if (
              rolling1.hash(i, j) in former_cache1
              and rolling2.hash(i, j) in former_cache2
          ):
              p = True
      # 区間[ok, ng) を更新
      if p:
          ok = m
      else:
          ng = m
  # whileループを抜けると区間[ok, ng)は[c, c + 1) になっている
  ans = ok
  
  print(ans)
  
problem_description: Statement
  
  We have a tree G with N vertices numbered 1 to N. The i-th edge of G connects
  Vertex a_i and Vertex b_i.
  
  Consider adding zero or more edges in G, and let H be the graph resulted.
  
  Find the number of graphs H that satisfy the following conditions, modulo
  998244353.
  
    * H does not contain self-loops or multiple edges.
    * The diameters of G and H are equal.
    * For every pair of vertices in H that is not directly connected by an edge, the addition of an edge directly connecting them would reduce the diameter of the graph.
samples: [{"input": "6\n    1 6\n    2 1\n    5 2\n    3 4\n    2 3", "output": "3\n    \n\nFor example, adding the edges (1, 5), (3, 5) in G satisfies the conditions.\n\n* * *"}, {"input": "3\n    1 2\n    2 3", "output": "1\n    \n\nThe only graph H that satisfies the conditions is G.\n\n* * *"}, {"input": "9\n    1 2\n    2 3\n    4 2\n    1 7\n    6 1\n    2 5\n    5 9\n    6 8", "output": "27\n    \n\n* * *"}, {"input": "19\n    2 4\n    15 8\n    1 16\n    1 3\n    12 19\n    1 18\n    7 11\n    11 15\n    12 9\n    1 6\n    7 14\n    18 2\n    13 12\n    13 5\n    16 13\n    7 1\n    11 10\n    7 17", "output": "78732"}]