Задача №113794. Электрическая цепь
На практических занятиях по физике в школе Женя проходит электричество. Очередная лабораторная работа состоит в анализе электрической цепи.
Электрическая цепь представляет собой набор узлов, соединенных проводами. Один из узлов является входом, а некоторый другой узел является выходом. При этом электрическая цепь в задании является хорошей.
Хорошей называется цепь, построенная по следующим правилам:
- Базовая цепь, состоящая только из входа и выхода, соединённых одним проводом, является хорошей.
- Если есть две хороших цепи A и B, то цепь S(A, B), составленная из них объединением выхода цепи A со входом цепи B, является хорошей. Входом получившейся цепи является вход цепи A, а выходом — выход цепи B.
- Если есть две хороших цепи A и B, то цепь P(A, B), составленная из них объединением входа A со входом B, а также выхода A с выходом B, является хорошей. Входом получившейся цепи является объединённый вход, а выходом — объединённый выход.
- Любая хорошая цепь может быть построена из базовых применением конечного числа предыдущих двух правил.
На рисунке приведены примеры хороших цепей.
Женя не очень любит физику, но очень любит теорию графов. Поэтому вместо выполнения задания, он хочет посчитать количество способов убрать из цепи некоторые провода так, чтобы оставшийся набор проводов образовывал дерево: от каждого узла до каждого существовал путь по проводам, причем единственный.
Так как количество может быть слишком большим, Женя хочет найти остаток от его деления на 998 244 353. Помогите Жене.
В первой строке дано два целых числа n и m — число узлов в сети и число проводов, соответственно (1 ≤ n, m ≤ 100 000).
В следующих m строках дано описание проводов. Каждая из них содержит два целых числа a и b, которые обозначают, что узлы a и b соединены проводом (1 ≤ a, b ≤ n; a ≠ b).
Гарантируется, что заданная цепь является хорошей. Входом цепи является узел с номером 1, а выходом — узел с номером n. Обратите внимание, что в хорошей цепи несколько проводов могут соединять одну и ту же пару узлов.
Выведите одно целое число — остаток от деления искомого количества способов на 998 244 353.
3 3
1 2
2 3
3 1
3
6 7
1 2
1 3
1 6
2 4
3 5
4 6
5 6
15
2 2
1 2
1 2
2
В первом и третьем примерах можно убрать один любой провод.
Во втором примере можно либо убрать провод (1, 6) и любой другой, либо по одному проводу из цепочек 1 - 2 - 4 - 6 и 1 - 3 - 5 - 6.