MianKing は $n$ 個のノードと $m$ 本の辺を持つグラフを持っており、$i$ 番目の辺 $(x_i, y_i)$ の重みは $w_i$ です。 グラフの最小全域木（Minimum Spanning Tree）とは、辺の重みの総和が最小となる全域木のことです。 MianKing は重み $w_1, \dots, w_m$ を忘れてしまいましたが、$w_1, \dots, w_m$ が $\{1, \dots, m\}$ の順列であることと、このグラフの最小全域木の辺集合が最初の $n-1$ 本の辺から構成されることは覚えています。 上記の条件を満たす $w_1, \dots, w_m$ が何通りあるかを計算して、MianKing を助けてください。答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

入力

1 行目に 2 つの整数 $n$ と $m$ ($2 \le n \le 20, n-1 \le m \le 100$) が与えられます。 続く $m$ 行には辺の情報が与えられ、$i$ 行目には 2 つの整数 $x_i$ と $y_i$ ($1 \le x_i, y_i \le n$) が含まれます。 辺 $(x_1, y_1), \dots, (x_{n-1}, y_{n-1})$ が $n$ 個のノードからなる木を形成することが保証されています。 グラフには多重辺や自己ループが含まれる可能性があることに注意してください。

出力

答えを $998\,244\,353$ で割った余りを出力してください。

入出力例

入力 1

3 3
1 2
2 3
3 1

出力 1

2

入力 2

4 5
1 2
2 3
2 4
1 4
1 2

出力 2

25

入力 3

3 6
1 2
2 3
1 1
1 1
1 1
1 1

出力 3

720