{"raw_statement":[{"iden":"problem statement","content":"You are given a simple undirected graph $G$ with $N$ vertices and $M$ edges (a simple graph does not contain self-loops or multi-edges). For $i = 1, 2, \\ldots, M$, the $i$\\-th edge connects vertex $u_i$ and vertex $v_i$.\nPrint the number of pairs of integers $(u, v)$ that satisfy $1 \\leq u \\lt v \\leq N$ and both of the following conditions.\n\n*   The graph $G$ does not have an edge connecting vertex $u$ and vertex $v$.\n*   Adding an edge connecting vertex $u$ and vertex $v$ in the graph $G$ results in a bipartite graph.\n\nWhat is a bipartite graph?An undirected graph is said to be **bipartite** if and only if one can paint each vertex black or white to satisfy the following condition.\n\n*   No edge connects vertices painted in the same color."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq M \\leq \\min \\lbrace 2 \\times 10^5, N(N-1)/2 \\rbrace$\n*   $1 \\leq u_i, v_i \\leq N$\n*   The graph $G$ is simple.\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_M$ $v_M$"},{"iden":"sample input 1","content":"5 4\n4 2\n3 1\n5 2\n3 2"},{"iden":"sample output 1","content":"2\n\nWe have two pairs of integers $(u, v)$ that satisfy the conditions in the problem statement: $(1, 4)$ and $(1, 5)$. Thus, you should print $2$.  \nThe other pairs do not satisfy the conditions. For instance, for $(1, 3)$, the graph $G$ has an edge connecting vertex $1$ and vertex $3$; for $(4, 5)$, adding an edge connecting vertex $4$ and vertex $5$ in the graph $G$ does not result in a bipartite graph."},{"iden":"sample input 2","content":"4 3\n3 1\n3 2\n1 2"},{"iden":"sample output 2","content":"0\n\nNote that the given graph may not be bipartite or connected."},{"iden":"sample input 3","content":"9 11\n4 9\n9 1\n8 2\n8 3\n9 2\n8 4\n6 7\n4 6\n7 5\n4 5\n7 8"},{"iden":"sample output 3","content":"9"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}