{"problem":{"name":"Make Bipartite 2","description":{"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_","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc282_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc282_d","tags":[],"sample_group":[["5 4\n4 2\n3 1\n5 2\n3 2","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."],["4 3\n3 1\n3 2\n1 2","0\n\nNote that the given graph may not be bipartite or connected."],["9 11\n4 9\n9 1\n8 2\n8 3\n9 2\n8 4\n6 7\n4 6\n7 5\n4 5\n7 8","9"]],"created_at":"2026-03-03 11:01:13"}}