Earthquake Damage 2

An earthquake has struck Farmer John's farm! The earthquake has damaged some of the pastures so that they are impassable. Remarkably, none of the cowpaths was damaged.

As usual, the farm is modeled as a set of $P$ ($1 \le P \le 3000$) pastures numbered $1 \dots P$, connected by a set of $C$ ($1 \le C \le 20000$) undirected cowpaths numbered $1 \dots C$. Cowpath $i$ connects pastures $a_i$ and $b_i$ ($1 \le a_i \le P$; $1 \le b_i \le P$). A cowpath might connect a pasture to itself, and two pastures might be connected by more than one cowpath. The barn is located in pasture $1$.

A total of $N$ ($1 \le N \le P$) cows, each in a different pasture, sequentially contact Farmer John by phone. Cow $j$ sends an integer report $report_j$ ($2 \le report_j \le P$) meaning that pasture $report_j$ is undamaged, but the calling cow cannot return to the barn from pasture $report_j$ because every path back to the barn passes through at least one damaged pasture.

After all cows have reported in, determine the minimum number of pastures that could be damaged. The barn (pasture $1$) and every reported pasture are guaranteed to be undamaged.

• Line $1$: Three space-separated integers: $P$, $C$, and $N$.
• Lines $2 \dots C+1$: Line $i+1$ describes cowpath $i$ with two integers $a_i$ and $b_i$.
• Lines $C+2 \dots C+N+1$: Line $C+1+j$ contains a single integer $report_j$.

• Line $1$: One integer, the minimum number of damaged pastures.