Електрична схема#3529
Андрій — початківець радіоаматор. Нещодавно у молодіжному науковому журналі «Юний винахідник» він побачив схему радіопередавача і вирішив зібрати її самостійно. Ця схема містить транзисторів, деякі з яких з'єднані між собою проводами. На схемі в журналі транзистори пронумеровані від до . Особливістю цієї схеми є те, що вона працює лише за умови правильного подання напруги — на -ий транзистор має бути подано вольт.
Андрій швидко зібрав схему за вказівками з журналу, але в процесі забув, на який транзистор подавати яку напругу. На схемі в журналі транзистори пронумеровані, а на зібраній схемі на столі — ні.
Тепер Андрій має визначити, яку напругу подавати на який транзистор, щоб схема працювала. Він не хоче перебирати всі можливі варіанти, а лише ті, які вважає розумними. Це означає, що він розгляне лише ті варіанти, для яких виконуються такі умови:
для кожного проводу в зібраній схемі вірно, що якщо напруга, подана на з'єднувані ним транзистори, становить вольт і вольт, то на схемі в журналі транзистори з номерами і також з'єднані;
якщо два транзистори, на які подано напругу вольт і вольт, не з'єднані проводом, то і на схемі в журналі транзистори з номерами і також не з'єднані.
Знайдіть кількість варіантів, які спробує Андрій.
Перший рядок вхідного файлу містить два цілі числа (2 \le n \le 8) і (0 \le m \le n(n-1)/2). Кожен з наступних рядків описує один з проводів і містить два цілі числа і — номери (зазначені на схемі в журналі) транзисторів, які з'єднані відповідним проводом (1 \le u, v \le n, u \ne v). Будь-які два транзистори з'єднані не більше ніж одним проводом.
У вихідний файл виведіть відповідь на задачу.
Приклад 1