题目描述

FJ 的农场里有 $p$ 个牧场，有 $c$ 条无向道路连接着他们，第 $i$ 条道路连接着两个牧场 $a_i$ 和 $b_i$，注意可能有很多条道路连接着相同的 $a_i$ 和 $b_i$，并且 $a_i$ 有可能和 $b_i$ 相等。FJ 在 $1$ 号牧场里。由于地震，某些牧场被损坏，但 $c$ 条道路没有一条损坏。有 $n$ 头奶牛，他们在不同的牧场里，他们一一向 FJ 报告。第 $i$ 头奶牛报告给 FJ 一个整数 $r_i$，代表第 $r_i$ 个牧场没有损毁，但不能够从第 $r_i$ 个牧场经过一些没有损坏的牧场到达 $1$ 号牧场。现在 FJ 想知道，最少有多少损坏的牧场。

输入格式

• 第一行：三个整数： $p,c,n$。

• 第 $2\sim c+1$ 行：每行两个整数 $a_i,b_i$。

• 第 $c+2 \sim c+n+1$ 行：第 $c+i+1$ 行包含一个整数：$r_i$。

输出格式

• 第一行：一个整数，代表最少有多少损坏的牧场。

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

1

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq p \leq 3000$，$1 \leq c \leq 20000$

题目来源

Usaco2009 Mar Gold