{"problem":{"name":"[ICPC 2018 Qingdao R]  Sub-cycle Graph","description":{"content":"Given an undirected simple graph with $n$ ($n \\ge 3$) vertices and $m$ edges where the vertices are numbered from 1 to $n$, we call it a ``sub-cycle`` graph if it's possible to add a non-negative numb","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9896"},"statements":[{"statement_type":"Markdown","content":"Given an undirected simple graph with $n$ ($n \\ge 3$) vertices and $m$ edges where the vertices are numbered from 1 to $n$, we call it a ``sub-cycle`` graph if it's possible to add a non-negative number of edges to it and turn the graph into exactly one simple cycle of $n$ vertices.\n\nGiven two integers $n$ and $m$, your task is to calculate the number of different sub-cycle graphs with $n$ vertices and $m$ edges. As the answer may be quite large, please output the answer modulo $10^9+7$.\n\nRecall that\n\n- A simple graph is a graph with no self loops or multiple edges;\n- A simple cycle of $n$ ($n \\ge 3$) vertices is a connected undirected simple graph with $n$ vertices and $n$ edges, where the degree of each vertex equals to 2;\n- Two undirected simple graphs with $n$ vertices and $m$ edges are different, if they have different sets of edges;\n- Let $u < v$, we denote $(u, v)$ as an undirected edge connecting vertices $u$ and $v$. Two undirected edges $(u_1, v_1)$ and $(u_2, v_2)$ are different, if $u_1 \\ne u_2$ or $v_1 \\ne v_2$.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ (about $2 \\times 10^4$), indicating the number of test cases. For each test case:\n\nThe first and only line contains two integers $n$ and $m$ ($3 \\le n \\le 10^5$, $0 \\le m \\le \\frac{n(n-1)}{2}$), indicating the number of vertices and the number of edges in the graph.\n\nIt's guaranteed that the sum of $n$ in all test cases will not exceed $3 \\times 10^7$.\n\n## Output\n\nFor each test case output one line containing one integer, indicating the number of different sub-cycle graphs with $n$ vertices and $m$ edges modulo $10^9+7$.\n\n[samples]\n\n## Note\n\nThe 12 sub-cycle graphs of the second sample test case are illustrated below.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/636hie1e.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9896","tags":["图论","2018","O2优化","组合数学","ICPC","青岛"],"sample_group":[["3\n4 2\n4 3\n5 3","15\n12\n90"]],"created_at":"2026-03-03 11:09:25"}}