output_description: Print the answer to the question: "Rng is going to a festival of what?"
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: N, M = map(int, input().split())
  edges = [[] for i in range(N)]
  for i in range(M):
      a, b = map(int, input().split())
      edges[a - 1] += [b - 1]
      edges[b - 1] += [a - 1]
  # print(edges)
  ans = 0
  # 奇数へいろを検出する0から(N//2)*2+1ステップ進んだ時, 0に戻れたらアウト
  m = (N // 2) * 2 + 1
  plist = [[] for i in range(m + 1)]
  plist[0] = [0]
  for i in range(m):  # iはステップ数
      for label in plist[i]:
          plist[i + 1] += edges[label]
      plist[i + 1] = list(set(plist[i + 1]))
  print(plist, plist[m])
  if 0 in plist[m]:
      print((N * (N - 1)) // 2 - M)  # 奇数要素の閉路があった場合は全ての頂点を結べる.
  else:
      if N % 2 == 0:
          n = N // 2
          print(n, n * (n - 1) - M)
      else:
          n1 = N // 2
          n2 = N // 2 + 1
          print(n1, n2)
          print((n1 * (n1 - 1)) // 2 + (n2 * (n2 - 1)) // 2 - M)
  
problem_description: Statement
  
  Rng is going to a festival.
  
  The name of the festival is given to you as a string S, which ends with
  `FESTIVAL`, from input. Answer the question: "Rng is going to a festival of
  what?" Output the answer.
  
  Here, assume that the name of "a festival of s" is a string obtained by
  appending `FESTIVAL` to the end of s. For example, `CODEFESTIVAL` is a
  festival of `CODE`.
samples: [{"input": "CODEFESTIVAL", "output": "CODE\n    \n\nThis is the same as the example in the statement.\n\n* * *"}, {"input": "CODEFESTIVALFESTIVAL", "output": "CODEFESTIVAL\n    \n\nThis string is obtained by appending `FESTIVAL` to the end of `CODEFESTIVAL`,\nso it is a festival of `CODEFESTIVAL`.\n\n* * *"}, {"input": "YAKINIKUFESTIVAL", "output": "YAKINIKU"}]