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.