Задачи
Электрическая схема
Электрическая схема
Андрей --- начинающий радиолюбитель. Недавно в журнале "Юный радиотехник" он увидел схему радиопередатчика и, разумеется, решил спаять такой радиопередатчик. Эта схема содержит \textbf{n} транзисторов, некоторые пары из которых соединены проводами. На рисунке в журнале транзисторы пронумерованы числами от \textbf{1} до \textbf{n}. Интересной особенностью этой схемы является то, что она работает только в том случае, если на ее элементы правильно подано напряжение --- на \textbf{i}-ый транзистор должно быть подано \textbf{i} вольт.
Андрей достаточно быстро спаял схему в соответствии с указаниями, приведенными в журнале. Однако он был недостаточно аккуратен и быстро забыл, на какой транзистор подавать какое напряжение. Дело в том, что на рисунке в журнале они пронумерованы, а на собранной схеме, которая лежит у него на столе --- нет.
Теперь перед Андреем стоит задача --- определить, какое напряжение надо подать на какой транзистор, чтобы схема работала. Он не хочет перебирать все способы подать напряжение, а хочет попробовать только те, которые считает разумными. Это означает, что он хочет попробовать только те варианты, для которых выполняются следующие условия:
\begin{itemize}
\item для каждого провода в собранной схеме верно, что если напряжение, поданное на соединяемые им транзисторы составляет \textbf{p} вольт и \textbf{q} вольт, то на схеме в журнале транзисторы с номерами \textbf{p} и \textbf{q} также соединены;
\item если два транзистора, на которые подано напряжение в \textbf{p} вольт и \textbf{q} вольт, не соединены проводом, то и на схеме в журнале транзисторы с номерами \textbf{p} и \textbf{q} также не соединены.
\end{itemize}
Найдите число вариантов, которые попробует Андрей.
\InputFile
Первая строка входного файла содержит два целых числа \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{8}) и \textbf{m} (\textbf{0} ≤ \textbf{m} ≤ \textbf{n(n−1)/2}). Каждая из последующих \textbf{m} строк описывает один из проводов и содержит два целых числа \textbf{u} и \textbf{v} --- номера (указанные на схеме в журнале) транзисторов, которые соединены соответствующим проводом (\textbf{1} ≤ \textbf{u}, \textbf{v} ≤ \textbf{n}, \textbf{u} ≠ \textbf{v}). Любые два транзистора соединены не более чем одним проводом.
\OutputFile
В выходной файл выведите ответ на задачу.
Входные данные #1
3 3 1 2 2 3 3 1
Выходные данные #1
6