Problem description

W życiu każdego licealisty nadchodzi ten wspaniały moment, gdy trzeba zacząć przygotowywać się do balu studniówkowego. Jak wiadomo, na studniówkę uczniowie najczęściej przychodzą w towarzystwie osoby płci przeciwnej. Wszyscy cieszą się na nadchodzące wydarzenie, tylko nie pan Janusz, dyrektor szkoły. Otrzymuje on wiele skarg od rodziców, że ich dzieci nie potrafią znaleźć sobie osoby towarzyszącej.

Pan Janusz postanowił rozwiązać ten problem. Dyrektor ma swoje zasady, na balu na pewno nie może przebywać żadna osoba spoza szkoły, to w końcu zbyt niebezpieczne. Na szczęście w szkole jest tyle samo chłopców co dziewcząt. Zatem pan Janusz postanowił, że sam ich dobierze w pary i problem będzie rozwiązany! Podekscytowany swoim pomysłem, nie zauważył, że takie dobranie w pary nie jest aż takie proste, w końcu nie wszyscy uczniowie się lubią. Ogłosił zatem zebranie uczniów i na bardzo długiej liście zapisał wszystkie pary damsko-męskie, które się lubią. Teraz chce wiedzieć, czy może tak dobrać uczniów w pary, aby nikt nie został samotny na bal i dodatkowo ile jest różnych możliwości takiego doboru. Pomóż dyrektorowi, bo sam nie jest w stanie uporać się z tym problemem.

Napisz program, który: wczyta opis listy znajomości stworzonej przez dyrektora, policzy ile jest możliwości poprawnego doboru uczniów w pary i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i M, oddzielone pojedynczym odstępem, oznaczające kolejno liczbę uczniów w szkole i długość listy par osób, które się lubią. W każdym z kolejnych M wierszy wejścia pojawia się opis jednej pary uczniów. Dla uproszczenia przyjmijmy, że chłopcy jak i dziewczęta są numerowani liczbami naturalnymi od 1 do N. Każdy opis składa się zatem z dwóch liczb naturalnych D_i i C_i, oddzielonych pojedynczym odstępem, oznaczających kolejno numer dziewczynki i numer chłopca z i-tej pary.

Dziewczynki oraz chłopcy numerowani są kolejnymi liczbami naturalnymi od 1 do N włącznie.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba całkowita K – liczba różnych sposobów doborów w pary chłopców i dziewcząt, tak aby każda dziewczyna była dobrana z dokładnie jednym chłopcem, a każdy chłopak z dokładnie jedną dziewczyną.

Jeśli różnych możliwości takich doborów w pary jest więcej niż 200 000, zamiast liczby K należy wypisać jedno słowo DUZO.

Ograniczenia

1 ≤ N ≤ 200, 0 ≤ M≤ N², 1 ≤ D_i, C_i ≤ N dla każdego i ∈ {1, 2, …, M}.

Przykład

4 8
1 1
2 2
2 3
3 2
3 4
4 2
4 3
4 4

3

3 4
1 1
2 1
3 2
3 3

0