output_description: Print the number of the connected components in the graph constructed by
  Takahashi.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N M
      u_1 v_1
      u_2 v_2
      :
      u_M v_M
attempt: import sys
  
  input = sys.stdin.readline
  
  N, M = map(int, input().split())
  edge = [[] for i in range(N)]
  for i in range(M):
      u, v = map(int, input().split())
      edge[u - 1].append(v - 1)
      edge[v - 1].append(u - 1)
  
  
  def is_bipartgraph():
      color = [0] * N
      used = [False] * N
      b = 0
      nb = 0
      for i in range(N):
          if not used[i]:
              flag = True
              stack = [(i, 1)]
              black = 0
              white = 0
              while stack:
                  v, c = stack.pop()
                  if not used[v]:
                      color[v] = c
                      black += c == 1
                      white += c == -1
                      used[v] = True
                      for nv in edge[v]:
                          if color[nv] == color[v]:
                              flag = False
                          elif color[nv] == 0:
                              stack.append((nv, -c))
              b += flag
              nb += not flag
      return (b, nb)
  
  
  a = 0
  for i in range(N):
      if not edge[i]:
          a += 1
  
  b, nb = is_bipartgraph()
  rest = N - (b + nb)
  b -= a
  print(a * N + nb * (a + nb + b) + b * (a + nb + 2 * b) + rest * a)
  
problem_description: Statement
  
  Takahashi has received an undirected graph with N vertices, numbered 1, 2,
  ..., N. The edges in this graph are represented by (u_i, v_i). There are no
  self-loops and multiple edges in this graph.
  
  Based on this graph, Takahashi is now constructing a new graph with N^2
  vertices, where each vertex is labeled with a pair of integers (a, b) (1 \leq
  a \leq N, 1 \leq b \leq N). The edges in this new graph are generated by the
  following rule:
  
    * Span an edge between vertices (a, b) and (a', b') if and only if both of the following two edges exist in the original graph: an edge between vertices a and a', and an edge between vertices b and b'.
  
  How many connected components are there in this new graph?
samples: [{"input": "3 1\n    1 2", "output": "7\n    \n\nThe graph constructed by Takahashi is as follows.\n\n![](https://atcoder.jp/img/agc011/6d34a4ddeba67b2286c00acda56abbcc.png)\n\n* * *"}, {"input": "7 5\n    1 2\n    3 4\n    3 5\n    4 5\n    2 6", "output": "18"}]