Mityng
Limit pamięci: 64 MB
Burmistrz Bajtogrodu w celu poprawienia swych notowań, postanowił zorganizować
mityng lekkoatletyczny. Niestety Bajtogród nie posiada stadionu, ani hali lekkoatletycznej,
zatem wszelkie konkurencje będą odbywały się na ulicach miasta. Burmistrz postanowił
ograniczyć się do konkurencji biegowych i poprosił Cię o wytyczenie tras.
Sieć drogowa Bajtogrodu składa się z skrzyżowań i łączących je ulic. Z każdego
skrzyżowania można dojechać ulicami do dowolnego innego.
Trasa biegowa musi zaczynać się na pewnym skrzyżowaniu, przebiegać pewną liczbą ulic
i kończyć się na innym skrzyżowaniu.
Burmistrz chce, aby w jednocześnie
odbywało się jak najwięcej konkurencji, należy więc wyznaczyć jak największą liczbę tras.
Z powodów bezpieczeństwa, żadne dwie trasy nie mogą mieć wspólnych skrzyżowań lub ulic.
Co więcej, nie wszystkie skrzyżowania nadają się do tego, by umieścić na nich start lub metę.
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita ()
oznaczająca liczbę skrzyżowań w Bajtogrodzie.
Skrzyżowania są numerowane od 1 do .
Kolejne wierszy zawiera opisy ulic:
każdy opis składa się z dwóch liczb całkowitych (, )
oznaczających, że skrzyżowania o numerach i są połączone ulicą.
W kolejnym wierszu znajduje się liczba całkowita () oznaczająca liczbę
skrzyżowań, na których można umieścić start lub metę. Ostatni wiersz wejścia zawiera liczb
oznaczających numery tych skrzyżowań.
Wyjście
W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą oznaczającą, ile maksymalnie
można wyznaczyć tras biegowych.
Przykład
Dla danych wejściowych:
5
1 2
3 2
4 1
1 5
4
1 2 5 4
poprawną odpowiedzią jest:
1
Autor zadania: Tomasz Idziaszek.