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.