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