Un séisme dans le Wisconsin a frappé la ferme de Farmer John ! Certains pâturages endommagés sont devenus impraticables. Étonnamment, aucun chemin de vaches n’a été endommagé.

La ferme comporte $P$ pâturages ($1 \le P \le 3,000$), numérotés $1..P$, reliés par $C$ chemins non orientés ($1 \le C \le 20,000$), numérotés $1..C$. Le chemin $i$ relie $a_{i}$ et $b_{i}$ ($1 \le a_{i} \le P; 1 \le b_{i} \le P$). Un chemin peut relier un pâturage à lui-même, et plusieurs chemins peuvent relier la même paire. La grange est dans le pâturage 1.

$N$ vaches ($1 \le N \le P$), dans des pâturages différents, contactent successivement Farmer John par téléphone mobile avec un entier $report_{j}$ ($2 \le report_{j} \le P$). Il indique que ce pâturage est intact, mais que la vache ne peut rejoindre la grange car elle ne trouve aucun trajet évitant les pâturages endommagés.

Après tous les rapports, trouvez le nombre minimal de pâturages endommagés.

Entrée

• Ligne 1 : trois entiers $P$, $C$ et $N$ séparés par des espaces.

• Lignes $2..C+1$ : la ligne $i+1$ décrit le chemin $i$ par les entiers $a_{i}$ et $b_{i}$.

• Lignes $C+2..C+N+1$ : la ligne $C+1$ $+$ $j$ contient l’entier $report_{j}$.

Sortie

• Ligne 1 : un nombre, le minimum de pâturages endommagés.

Exemples

Entrée 1

5 5 2
1 2
2 3
3 5
2 4
4 5
4
5

Sortie 1

1

Remarque

Le pâturage 2 seul endommagé donne cette situation.

Auteurs du problème : Hal Burch, Richard Peng, 2008