威斯康星發生了地震,波及 Farmer John 的農場!地震損壞了部分牧場,使它們無法通行。出人意料的是,沒有一條奶牛小路受損。
和往常一樣,農場由 $P$ 個牧場($1 \le P \le 3,000$,編號 $1..P$)及連接它們的 $C$ 條無向奶牛小路($1 \le C \le 20,000$,編號 $1..C$)組成。小路 $i$ 連接牧場 $a_{i}$ 和 $b_{i}$($1 \le a_{i} \le P; 1 \le b_{i} \le P$)。小路可能把 $a_{i}$ 連到它自身,也可能多次連接同一對牧場。牛棚位於牧場 1。
總共 $N$ 頭位於不同牧場的奶牛($1 \le N \le P$)依次用手機聯絡 Farmer John,傳送整數訊息 $report_{j}$($2 \le report_{j} \le P$)。它表示牧場 $report_{j}$ 未損壞,但這頭奶牛無法從那裡返回牛棚,因為找不到不經過損壞牧場的路徑。
所有奶牛報告完畢後,求至少有多少個牧場被損壞。
輸入格式
第 1 行:三個以空格分隔的整數 $P$、$C$ 和 $N$。
第 $2..C+1$ 行:第 $i+1$ 行以兩個整數 $a_{i}$ 和 $b_{i}$ 描述小路 $i$。
第 $C+2..C+N+1$ 行:第 $C+1$ $+$ $j$ 行包含一個整數 $report_{j}$。
輸出格式
- 第 1 行:一個數,表示損壞牧場的最少數量。
範例
輸入格式 1
5 5 2
1 2
2 3
3 5
2 4
4 5
4
5
輸出格式 1
1
說明
只有牧場 2 損壞就能產生這種情況。
題目作者:Hal Burch、Richard Peng,2008