{"problem":{"name":"3 Steps","description":{"content":"Rng has a connected undirected graph with $N$ vertices. Currently, there are $M$ edges in the graph, and the $i$\\-th edge connects Vertices $A_i$ and $B_i$. Rng will add new edges to the graph by repe","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"code_festival_2017_qualb_c"},"statements":[{"statement_type":"Markdown","content":"Rng has a connected undirected graph with $N$ vertices. Currently, there are $M$ edges in the graph, and the $i$\\-th edge connects Vertices $A_i$ and $B_i$.\nRng will add new edges to the graph by repeating the following operation:\n\n*   Operation: Choose $u$ and $v$ $(u \\neq v)$ such that Vertex $v$ can be reached by traversing exactly three edges from Vertex $u$, and add an edge connecting Vertices $u$ and $v$. It is not allowed to add an edge if there is already an edge connecting Vertices $u$ and $v$.\n\nFind the maximum possible number of edges that can be added.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq A_i,B_i \\leq N$\n*   The graph has no self-loops or multiple edges.\n*   The graph is connected.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$:$\n$A_M$ $B_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"code_festival_2017_qualb_c","tags":[],"sample_group":[["6 5\n1 2\n2 3\n3 4\n4 5\n5 6","4\n\nIf we add edges as shown below, four edges can be added, and no more.\n![image](https://img.atcoder.jp/code-festival-2017-qualb/6e99dccc06ac8b14d9ca2e297524bc0c.png)"],["5 5\n1 2\n2 3\n3 1\n5 4\n5 1","5\n\nFive edges can be added, for example, as follows:\n\n*   Add an edge connecting Vertex $5$ and Vertex $3$.\n*   Add an edge connecting Vertex $5$ and Vertex $2$.\n*   Add an edge connecting Vertex $4$ and Vertex $1$.\n*   Add an edge connecting Vertex $4$ and Vertex $2$.\n*   Add an edge connecting Vertex $4$ and Vertex $3$."]],"created_at":"2026-03-03 11:01:14"}}