A. Парк аттракционов
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вас наняли руководить разработкой проекта нового парка аттракционов. В парке будет некоторая изюминка: от одного аттракциона к другому посетителей будут доставлять специальные направленные спуски.

Владелец парка передал вам текущий проект: список планируемых к постройке аттракционов и список спусков, которые должны быть построены. Так как он предприниматель, то он, как обычно, вообразил невозможное: кроме всего прочего, он запланировал спуск от замка с привидениями к американским горкам, спуск от американских горок к башни свободного падения, а также спуск от башни свободного падения к замку с привидениями. Так как спуски могут вести только вниз, очевидно, что это невозможно. У вас нет привилегий игнорировать законы физики при постройке парка, поэтому в проект нужно внести изменения. Может, владелец примет изменение направления спуска между башней и замком?

Формально:

  • Проектом называется список аттракционов и список направленных спусков. Каждый спуск начинается около одного аттракциона и заканчивается у другого.
  • Предложение получается из проекта изменением направлений некоторых спусков (возможно, ни одного или всех).
  • Предложение корректно, если существует способ выбрать высоты расположений всех аттракционов так, чтобы все спуски вели вниз.
  • Стоимостью предложения называется количество спусков, направление которых нужно изменить.

Для данного проекта найдите сумму стоимостей всех корректных предложений по модулю $$$998,244,353$$$.

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

Первая строка содержит два целых числа $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 18$$$, $$$0 \leq m \leq n(n-1)/2$$$) — количество аттракционов и количество спусков, соответственно. Аттракционы пронумерованы от $$$1$$$ до $$$n$$$.

Далее следуют $$$m$$$ строк. $$$i$$$-я из этих строк содержит два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$), обозначающие спуск от $$$a_i$$$ к $$$b_i$$$.

Можете рассчитывать, что:

  • Нет петель, то есть для всех $$$i$$$ выполняется $$$a_i \neq b_i$$$.
  • Никакой спуск не встречается дважды, то есть для всех $$$i \neq j$$$ выполняется $$$a_i \neq a_j$$$ или $$$b_i \neq b_j$$$.)
  • Никакая пара аттракционов не соединена в обоих направлениях, то есть неупорядоченные пары $$$\{a_i, b_i\}$$$ различны.
Выходные данные

Выведите одно целое число — сумму стоимостей всех корректных предложений по модулю $$$998,244,353$$$.

Система оценки

Подзадача 1 (7 баллов): $$$n \leq 3$$$

Подзадача 2 (12 баллов): $$$n \leq 6$$$

Подзадача 3 (23 балла): $$$n \leq 10$$$

Подзадача 4 (21 балл): $$$n \leq 15$$$

Подзадача 5 (37 баллов): нет дополнительных ограничений

Примеры
Входные данные
2 1
1 2
Выходные данные
1
Входные данные
3 3
1 2
2 3
1 3
Выходные данные
9
Примечание

В первом примере есть два предложения:

  • Направление спуска не изменено. Стоимость $$$0$$$.
  • Направление спуска изменено. Стоимость $$$1$$$.
Так как оба предложения корректны, то ответ равен $$$0 + 1 = 1$$$.

Во втором примере есть восемь предложений, где спуски направлены так:

  • $$$1 \rightarrow 2$$$, $$$2 \rightarrow 3$$$, $$$1 \rightarrow 3$$$ (стоимость $$$0$$$)
  • $$$1 \rightarrow 2$$$, $$$2 \rightarrow 3$$$, $$$3 \rightarrow 1$$$ (стоимость $$$1$$$)
  • $$$1 \rightarrow 2$$$, $$$3 \rightarrow 2$$$, $$$1 \rightarrow 3$$$ (стоимость $$$1$$$)
  • $$$1 \rightarrow 2$$$, $$$3 \rightarrow 2$$$, $$$3 \rightarrow 1$$$ (стоимость $$$2$$$)
  • $$$2 \rightarrow 1$$$, $$$2 \rightarrow 3$$$, $$$1 \rightarrow 3$$$ (стоимость $$$1$$$)
  • $$$2 \rightarrow 1$$$, $$$2 \rightarrow 3$$$, $$$3 \rightarrow 1$$$ (стоимость $$$2$$$)
  • $$$2 \rightarrow 1$$$, $$$3 \rightarrow 2$$$, $$$1 \rightarrow 3$$$ (стоимость $$$2$$$)
  • $$$2 \rightarrow 1$$$, $$$3 \rightarrow 2$$$, $$$3 \rightarrow 1$$$ (стоимость $$$3$$$)

Второе предложение некорректно, так как есть последовательность спусков $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 1$$$. Это означает, что аттракцион $$$1$$$ должен быть строго выше чем он сам, что, очевидно, невозможно. Аналогично, седьмое предложение тоже некорректно. Поэтому ответ равен $$$0 + 1 + 2 + 1 + 2 + 3 = 9$$$.