У MianKing есть граф с $n$ вершинами и $m$ ребрами, где $i$-е ребро $(x_i, y_i)$ имеет вес $w_i$. Минимальное остовное дерево графа — это остовное дерево с минимальной суммой весов ребер. MianKing забыл веса $w_1 \dots w_m$, но он помнит, что $w_1 \dots w_m$ являются перестановкой чисел $\{1 \dots m\}$ и что множество ребер минимального остовного дерева этого графа состоит из первых $n - 1$ ребер. Вам нужно помочь MianKing вычислить, сколько существует перестановок $w_1 \dots w_m$, удовлетворяющих вышеуказанным условиям. Ответ может быть очень большим, поэтому выведите его по модулю $998\,244\,353$.

Входные данные

Первая строка содержит два целых числа $n$ и $m$ ($2 \le n \le 20$, $n - 1 \le m \le 100$). Далее следуют $m$ строк, где $i$-я строка содержит два целых числа $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