Dziuple

Limit pamięci: 64 MB

W Bajtocji rosną dwa bardzo wysokie pionowe drzewa, a w każdym z nich są wydrążone jedna pod drugą dziuple dla ptaków. Pewnego dnia w dziuplach postanowiło zamieszkać bardzo szybkich ptaszków. Niektóre ptaszki znają się wzajemnie, więc po wprowadzeniu się chciałyby mieć możliwość odwiedzania się nawzajem w swoich dziuplach. Ptaszki latają bardzo szybko i zawsze po liniach prostych. Chcąc uniknąć niebezpieczeństwa zderzenia postanowiły rozlokować się w dziuplach w taki sposób, żeby:

• każde dwa ptaszki, które chciałyby się odwiedzać, mieszkały na różnych drzewach, oraz
• dla dowolnych dwóch par znajomych ptaszków, odcinki łączące dziuple znajomych ptaszków nie przecinały się (co najwyżej mogą mieć wspólny koniec).

Jak wiadomo, ptaszki mają niewielkie rozumki. Dlatego też poprosiły Cię - znanego ornitologa - o pomoc w sprawdzeniu, na ile różnych sposobów mogą rozlokować się w dziuplach.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis relacji znajomości wśród ptaszków,
• obliczy, na ile różnych sposobów można rozmieścić ptaszki w dziuplach spełniając podane powyżej wymagania,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia zapisano trzy liczby całkowite , oraz , oznaczające odpowiednio: liczbę ptaszków, liczbę różnych par ptaszków znających się nawzajem oraz liczbę której należy użyć przy podawaniu wyniku (por. p. Wyjście), , , . Ptaszki są ponumerowane od do . W kolejnych wierszach podane są pary znających się nawzajem ptaszków, po jednej parze w wierszu. W -ym wierszu są zapisane dwie liczby całkowite i oddzielone pojedynczym odstępem, , . Są to numery znajomych ptaszków. Każda (nieuporządkowana) para znajomych ptaszków jest podana dokładnie raz.

Wyjście

Niech będzie liczbą różnych rozmieszczeń ptaszków w dziuplach, spełniających podane warunki. Twój program powinien wypisać w pierwszym wierszu wyjścia jedną liczbę całkowitą: resztę z dzielenia przez . Jeżeli nie istnieje szukane rozmieszczenie ptaszków, to poprawnym wynikiem jest .

Przykład

Dla danych wejściowych:

3 2 10
1 2
1 3

poprawną odpowiedzią jest:

4

Autor zadania: Jakub Radoszewski.