Zadanie: Dziuple
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ć n 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).
Dodatkowo, ptaszki chcą mieszkać jak najniżej.
Na każdym z drzew zajmują więc pewną liczbę dolnych dziupli.
W każdym z drzew jest więcej dziupli niż wszystkich ptaszków.
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
n, m oraz k, 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),
2 <= n <= 1 000 000,
1 <= m <= 10 000 000,
2 <= k <= 2 000 000.
Ptaszki są ponumerowane od 1 do n.
W kolejnych m wierszach podane są pary znających się nawzajem
ptaszków, po jednej parze w wierszu.
W i + 1-ym wierszu są zapisane dwie liczby całkowite ai i bi
oddzielone pojedynczym odstępem,
1 <= ai, bi <= n,
ai <> bi.
Są to numery znajomych ptaszków.
Każda (nieuporządkowana) para znajomych ptaszków jest podana
dokładnie raz.
Wyjście
Niech r 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 r przez k.
Jeżeli nie istnieje szukane rozmieszczenie ptaszków, to poprawnym
wynikiem jest 0.
Przykład
Dla danych wejściowych:3 2 10
1 2
1 3
poprawną odpowiedzią jest:4