21078번 - Minimum Spanning Tree 다국어

MianKing has a graph with $n$ nodes and $m$ edges, where the $i$-th edge $(x_i, y_i)$ has an edge weight of $w_i$.

The Minimum Spanning Tree of the graph is a spanning tree with the minimum sum of edge weights.

MianKing forgot the weights $w_{1...m}$, but he still remembers that $w_{1...m}$ are a permutation of $\{1...m\}$ and that the edge set of the Minimum Spanning Tree of this graph consists of the first $n - 1$ edges.

Now you need to help MianKing to calculate how many $w_{1...m}$ satisfy the conditions above. The answer may be very large, so you only need to output the answer modulo $998\,244\,353$.

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 20$, $n - 1 \leq m \leq 100$).

Then there are $m$ lines, where the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$).

It is guaranteed that the edges $(x_1, y_1)$, $\ldots$, $(x_{n - 1}, y_{n - 1})$ form a tree with $n$ nodes.

Note that the graph may have multiple edges and self-loops.

Output the answer modulo $998\,244\,353$.