Krasnale

To zadanie pochodzi z Kółka Informatycznego w Staszicu.

Rodzina krasnali co wieczór gromadzi się na kolacji i zasiada przy długim stole. Wszyscy siadają z jednej strony stołu w pewnej kolejności. Miejsca przy stole nie są równoważne, gdyż jeden jego koniec znajduje się bliżej kuchni. A im bliżej kuchni ktoś siedzi, tym wcześniej dostanie jedzenie. Ponadto zdarza się, że jakiś krasnal uważa się za bardziej zasłużonego od innego krasnala - powinien on wtedy siedzieć bliżej kuchni.

Co wieczór rozmieszczenie krasnali przy stole jest inne. Policz, na ile dni starczy im różnych ustawień.

Zadanie

Napisz program który:

  • wczyta ze standardowego wejścia liczbę krasnali oraz informację, które krasnale uważają się za bardziej zasłużonych od których,
  • wyznaczy liczbę różnych poprawnych rozmieszczeń krasnali przy stole,
  • wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite nieujemne n i m (1 <= n <= 19). Pierwsza z nich oznacza liczbę krasnali, a druga to liczba zależności. W każdym z kolejnych m wierszy znajdują się dwie różne liczby całkowite x_i, y_i (1 <= x_i, y_i <= n) oznaczające, że krasnal x_i uważa się za bardziej zasłużonego niż krasnal y_i. Każda para podana jest co najwyżej raz. Krasnale są ponumerowani od 1 do n.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znajdować dokładnie jedna liczba całkowita - liczba różnych poprawnych rozmieszczeń krasnali przy stole.

Przykład

Dla danych:

3 1
1 2

prawidłową odpowiedzią jest:

3