MianKing possède un graphe avec $n$ sommets et $m$ arêtes, où la $i$-ième arête $(x_i, y_i)$ a un poids $w_i$. L'arbre couvrant minimal (Minimum Spanning Tree) du graphe est un arbre couvrant dont la somme des poids des arêtes est minimale. MianKing a oublié les poids $w_1 \dots m$, mais il se souvient encore que $w_1 \dots m$ sont une permutation de $\{1 \dots m\}$ et que l'ensemble des arêtes de l'arbre couvrant minimal de ce graphe est constitué des $n - 1$ premières arêtes. Vous devez maintenant aider MianKing à calculer combien de permutations $w_1 \dots m$ satisfont les conditions ci-dessus. La réponse peut être très grande, vous devez donc uniquement afficher la réponse modulo $998\,244\,353$.

Entrée

La première ligne contient deux entiers $n$ et $m$ ($2 \le n \le 20$, $n - 1 \le m \le 100$). Ensuite, il y a $m$ lignes, où la $i$-ième ligne contient deux entiers $x_i$ et $y_i$ ($1 \le x_i, y_i \le n$). Il est garanti que les arêtes $(x_1, y_1), \dots, (x_{n-1}, y_{n-1})$ forment un arbre avec $n$ sommets. Notez que le graphe peut contenir des arêtes multiples et des boucles.

Sortie

Affichez la réponse modulo $998\,244\,353$.

Exemples

Entrée 1

3 3
1 2
2 3
3 1

Sortie 1

2

Entrée 2

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

Sortie 2

25

Entrée 3

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

Sortie 3

720