Impreza
Limit pamięci: 256 MB
Wielkimi krokami zbliża się koniec roku szkolnego. Kinga postanowiła z
tej okazji zorganizować imprezę w gronie klasowym. W klasie Kingi, niestety jak
to czasem bywa, można zauważyć pewne podziały. Pomimo że większość par
uczniów w klasie bardzo się lubi, niektórzy, delikatnie mówiąc, niespecjalnie za
sobą przepadają. Kinga jest natomiast bardzo pogodną osobą - lubi całą swoją
klasę i bardzo sobie ceni przyjaźń, którą okazują jej koledzy. Wie, że jeśli
zaprosi Andrzeja i Szymka, to chłopaki się pobiją i przyjęcie się nie uda.
Jeśli zaś nie zaprosi Szymka, ale zaprosi Krzyśka, który koleguje się z
Szymkiem, to Szymek zapewne dowie się o imprezie od swojego kolegi, będzie miał
żal do Kingi i natychmiast przestanie ją lubić. Co za ludzie!
Podsumowując, Kinga nie chce widzieć na imprezie pary wrogów, ale nie
może też nie zaprosić przyjaciela pewnej zaproszonej osoby. Ponadto Kinga
chciałaby zaprosić jak najwięcej kolegów. Pomóż jej obliczyć maksymalną liczbę
zaproszonych gości, a także liczbę możliwych sposobów wyboru najliczniejszej
listy zaproszonych.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite
, oraz (, , ), oznaczające odpowiednio
liczbę osób w klasie Kingi, liczbę par przyjaciół i liczbę par wrogów w klasie.
Dla uproszczenia, kolegów Kingi numerujemy liczbami od do . W każdym z
następnych wierszy znajdują się po dwie liczby całkowite i () oznaczające, że przyjaźni się z .
Każdy z kolejnych wierszy zawiera po dwie liczby całkowite oraz
() oznaczające, że nie lubi się z
. Żadna nieuporządkowana para osób nie powtórzy się na wejściu.
Wyjście
W pierwszym i jedynym wierszu wejścia powinny znaleźć się dwie liczby
całkowite. Pierwsza to maksymalna możliwa liczba zaproszonych przez Kingę
gości, a druga - liczba sposobów wyboru tej liczby gości.
Przykład
Dla danych wejściowych:
6 10 2
1 2
1 3
4 1
1 5
2 5
3 2
2 4
3 4
3 5
5 4
2 6
5 6
poprawną odpowiedzią jest:
5 1
Autor zadania: Adam Karczmarz.