{"problem":{"name":"[ICPC 2021 Nanjing R] Ancient Magic Circle in Teyvat","description":{"content":"Astrologist Mona Megistus discovers an ancient magic circle in Teyvat recently. ![](https://cdn.luogu.com.cn/upload/image_hosting/gohzab6t.png) The magic circle looks like a complete graph with $n$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9850"},"statements":[{"statement_type":"Markdown","content":"Astrologist Mona Megistus discovers an ancient magic circle in Teyvat recently.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/gohzab6t.png)\n\nThe magic circle looks like a complete graph with $n$ vertices, where $m$ edges are colored red and other edges are colored blue. Note that a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.\n\nMona realizes that if she chooses four different vertices such that the six edges between these four vertices are of the same color, she will get a *key* from the magic circle. If the color is red, she will get a *red key*, and if the color is blue, she will get a *blue key*.\n\nBase on the information written in the ancient books Mona has read, the magic power of the ancient magic circle is the absolute difference between the number of *red keys* and the number of the number of *blue keys* she can get from the magic circle.\n\nMona needs your help badly, since calculating the magic power of the magic circle is really a tough job.\n\n## Input\n\nThere is only one test case in each test file.\n\nThe first line of the input contains two integers $n$ and $m$ ($4 \\le n \\le 10^5$, $0 \\le m \\le \\min(\\frac{n(n-1)}{2}, 2 \\times 10^5)$) indicating the number of vertices and the number of edges colored red of the ancient magic circle.\n\nFor the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($u_i < v_i$) indicating a red edge connecting vertices $u_i$ and $v_i$. It is guaranteed that each edge appears at most once.\n\n## Output\n\nOutput one line containing one integer indicating the magic power of the ancient magic circle.\n\n[samples]\n\n## Note\n\nFor the sample case, there is only one *red key* $(1,2,3,4)$ and there are four *blue keys* $(1,5,6,7)$, $(2,5,6,7)$, $(3,5,6,7)$ and $(4,5,6,7)$ in the ancient magic circle, thus the magic power of the magic circle is $|1-4|=3$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9850","tags":["图论","2021","Special Judge","O2优化","容斥原理","ICPC","南京"],"sample_group":[["7 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n","3\n"]],"created_at":"2026-03-03 11:09:25"}}