A data center has n server racks, numbered 1 to n. A technician laid m two-way cables, numbered 1 to m in the order given. Cables are undirected and may connect a rack to itself or duplicate another cable's endpoints.
A diagnostic later found that f of those cables are faulty: a faulty cable carries no signal at all and must be treated as if it were never installed. You are given the numbers (1-indexed positions in the cable list) of the faulty cables.
Using only the working (non-faulty) cables, some racks may already be connected into groups. Determine the minimum number of BRAND-NEW cables that must be added (each new cable can connect any two racks you choose) so that every rack ends up connected to every other rack, directly or indirectly.
Input format
Line 1: three integers n, m, f — number of racks (1-indexed), number of cables, and number of faulty cables.
Next m lines: two integers — cable number (1-indexed by order of appearance, starting at 1) connects rack and rack .
Last line: integers — the 1-indexed positions (into the cable list above) of the faulty cables. This line is empty if .
Output format
A single integer: the minimum number of new cables needed to fully connect all n racks using only the non-faulty existing cables plus new ones.
Constraints
- 1 ≤ n ≤ 20
- 0 ≤ m ≤ 40
- 0 ≤ f ≤ m
- 1 ≤ u, v ≤ n
- the
ffaulty positions are distinct values in[1, m]