{"problem":{"name":"Edge Ordering","description":{"content":"You are given a simple connected undirected graph $G$ consisting of $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the edges are numbered $1$ to $M$. Edge $i$ connects Vertex $a","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"diverta2019_f"},"statements":[{"statement_type":"Markdown","content":"You are given a simple connected undirected graph $G$ consisting of $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the edges are numbered $1$ to $M$.\nEdge $i$ connects Vertex $a_i$ and $b_i$ bidirectionally. It is guaranteed that the subgraph consisting of Vertex $1,2,\\ldots,N$ and Edge $1,2,\\ldots,N-1$ is a spanning tree of $G$.\nAn allocation of weights to the edges is called a _good allocation_ when the tree consisting of Vertex $1,2,\\ldots,N$ and Edge $1,2,\\ldots,N-1$ is a minimum spanning tree of $G$.\nThere are $M!$ ways to allocate the edges distinct integer weights between $1$ and $M$. For each good allocation among those, find the total weight of the edges in the minimum spanning tree, and print the sum of those total weights modulo $10^{9}+7$.\n\n## Constraints\n\n*   All values in input are integers.\n*   $2 \\leq N \\leq 20$\n*   $N-1 \\leq M \\leq N(N-1)/2$\n*   $1 \\leq a_i, b_i \\leq N$\n*   $G$ does not have self-loops or multiple edges.\n*   The subgraph consisting of Vertex $1,2,\\ldots,N$ and Edge $1,2,\\ldots,N-1$ is a spanning tree of $G$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$\\vdots$\n$a_M$ $b_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"diverta2019_f","tags":[],"sample_group":[["3 3\n1 2\n2 3\n1 3","6\n\nAn allocation is good only if Edge $3$ has the weight $3$. For these good allocations, the total weight of the edges in the minimum spanning tree is $3$, and there are two good allocations, so the answer is $6$."],["4 4\n1 2\n3 2\n3 4\n1 3","50"],["15 28\n10 7\n5 9\n2 13\n2 14\n6 1\n5 12\n2 10\n3 9\n10 15\n11 12\n12 6\n2 12\n12 8\n4 10\n15 3\n13 14\n1 15\n15 12\n4 14\n1 7\n5 11\n7 13\n9 10\n2 7\n1 9\n5 6\n12 14\n5 2","657573092\n\nPrint the sum of those total weights modulo $10^{9}+7$."]],"created_at":"2026-03-03 11:01:14"}}