Ранок HaHa#3791
HaHa сьогодні дуже радий, адже він збирається взяти участь у -му Програмістському Конкурсі Університету Хунань. Він прокинувся вранці і хотів якомога швидше дістатися до Університету Хунань, але зрозумів, що йому ще потрібно виконати завдань перед тим, як вирушити в дорогу.
Спочатку HaHa подумав, що існує (факторіал від ) способів виконати всі завдання, однак швидко зрозумів, що це неможливо через деякі дратівливі обмеження: деякі завдання потрібно виконати перед іншими. Тепер HaHa цікавиться, скільки існує способів виконати всі завдання, і він просить вас про допомогу. Ваше завдання - визначити кількість способів завершити його роботу.
Є декілька тестових випадків, кожен з яких містить декілька рядків. Перший рядок кожного випадку містить два натуральні числа (як описано вище) та M \leq 400 (загальна кількість обмежень для завдань).
Наступні рядків описують обмеження, де кожен рядок містить два додатні цілі числа та , що означає, що -те завдання повинно бути виконане перед -тим завданням.
Вхідні дані завершуються кінцем файлу. Гарантовано, що 1 \leq A, B \leq N \leq 17.
Для кожного випадку виведіть одне число: кількість способів завершити роботу.
Приклад 1