{"problem":{"name":"Triangle Toggle","description":{"content":"There is a complete graph with $N$ vertices numbered $1$ to $N$. Each edge is colored black or white. For $i=1,2,\\ldots,M$, the edge connecting vertices $U_i$ and $V_i$ is colored black, and all other","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc205_b"},"statements":[{"statement_type":"Markdown","content":"There is a complete graph with $N$ vertices numbered $1$ to $N$. Each edge is colored black or white. For $i=1,2,\\ldots,M$, the edge connecting vertices $U_i$ and $V_i$ is colored black, and all other edges are colored white.\nYou can perform the following operation zero or more times.\n\n*   Choose a triple of integers $(a,b,c)$ satisfying $1\\le a < b < c \\le N$, and repaint each of the following three edges: white to black, black to white.\n    *   The edge connecting vertices $a$ and $b$\n    *   The edge connecting vertices $b$ and $c$\n    *   The edge connecting vertices $a$ and $c$\n\nFind the maximum number of edges that can be colored black when you perform operations appropriately.\n\n## Constraints\n\n*   $3\\le N\\le 2\\times 10^5$\n*   $\\displaystyle 0\\le M\\le 2\\times 10^5$\n*   $1\\le U_i < V_i \\le N$\n*   $(U_i , V_i) \\neq (U_j , V_j)$ $(i \\neq j)$\n*   All input values 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":"arc205_b","tags":[],"sample_group":[["4 1\n1 2","5\n\nBy performing two operations as follows, you can make the number of black edges $5$.\n\n*   Choose $(a,b,c)=(1,3,4)$. Then, we have the following four black edges.\n    *   The edge connecting vertices $1$ and $2$\n    *   The edge connecting vertices $1$ and $3$\n    *   The edge connecting vertices $1$ and $4$\n    *   The edge connecting vertices $3$ and $4$\n*   Choose $(a,b,c)=(2,3,4)$. Then, we have the following five black edges.\n    *   The edge connecting vertices $1$ and $2$\n    *   The edge connecting vertices $1$ and $3$\n    *   The edge connecting vertices $1$ and $4$\n    *   The edge connecting vertices $2$ and $3$\n    *   The edge connecting vertices $2$ and $4$\n\nYou cannot make the number of black edges more than $5$, so output $5$."],["7 3\n1 2\n2 3\n3 6","20"],["123123 0","7579575003\n\nBe careful about overflow."]],"created_at":"2026-03-03 11:01:14"}}