Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

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




Wersja do druku