{"trustable":false,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"给定一个包含 `n` (n ≥ 3) 个顶点,`m` 条边的无向简单图,如果我们可以在上面添加0条或多条边使得图变成一个 `n` 元简单环,我们称它为次环图。\n\n给定数字 `n, m`,你的任务是计算 `n` 个顶点 `m` 条边的次环图的数量。由于答案可能十分庞大,请对 10\u003csup\u003e9\u003c/sup\u003e+7 取模。\n\n请注意:\n\n- 一个简单图不包含自环或者重边\n- 一个 `n` 个顶点构成的简单环包含 `n` 条边,并且每个顶点的度为2。\n- 两个`n`点`m`边的简单图不同,是指两者的边集不同。\n- 令 u\u003csub\u003ei\u003c/sub\u003e \u0026lt; v\u003csub\u003ei\u003c/sub\u003e,两个无向边 (u\u003csub\u003e1\u003c/sub\u003e, v\u003csub\u003e1\u003c/sub\u003e) 和 (u\u003csub\u003e2\u003c/sub\u003e, v\u003csub\u003e2\u003c/sub\u003e) 被视作不同,如果 u\u003csub\u003e1\u003c/sub\u003e ≠ u\u003csub\u003e2\u003c/sub\u003e 或者 v\u003csub\u003e1\u003c/sub\u003e ≠ v\u003csub\u003e2\u003c/sub\u003e。"}},{"title":"输入","value":{"format":"MD","content":"输入包含多组测试用例,第一行含有一个数字 `T`(大约为 2 \u0026times; 10\u003csup\u003e4\u003c/sup\u003e),表示测试用例的数量。\n\n对于每组测试用例,一行包含两个数字 `n, m` (3 ≤ n ≤ 10\u003csup\u003e5\u003c/sup\u003e, 0 ≤ m ≤ n(n-1)/2),表示图中顶点数量和边的数量。\n\n保证所有测试用例的 `n` 的和不超过 3 \u0026times; 10\u003csup\u003e7\u003c/sup\u003e。"}},{"title":"输出","value":{"format":"MD","content":"对于每组测试用例,输出一行一个数字,表示 `n` 个顶点 `m` 条边的不同次环图数量对 10\u003csup\u003e9\u003c/sup\u003e+7 取模。"}},{"title":"样例输入","value":{"format":"MD","content":"```\n3\n4 2\n4 3\n5 3\n```"}},{"title":"样例输出","value":{"format":"MD","content":"```\n15\n12\n90\n```"}},{"title":"提示","value":{"format":"MD","content":"第二个样例的12个次环图如下所示。\n\n\u003cimg SRC\u003d\"CDN_BASE_URL/beb30ba3436ec3ec9b54ba4838726590?v\u003d1565829283\" width\u003d\"700px\"\u003e \n "}}]}