#C4207. Isolating Critical Rooms

    ID: 47720 Type: Default 1000ms 256MiB

Isolating Critical Rooms

Isolating Critical Rooms

You are given a network of rooms represented as an undirected graph with n nodes and m edges. A subset of these rooms are marked as critical and must be isolated from the rest of the network. In one isolation operation, you can remove a critical room from the graph. Your task is to determine the minimum number of isolation operations required so that each critical room is effectively isolated from all other rooms.

Note: For this problem, the answer is simply the number of critical rooms that exist in the network (i.e. the number of isolation operations needed), since each operation isolates exactly one critical room.

The graph details are provided even though they do not affect the answer directly. The input consists of several datasets. For each dataset, first the number of rooms n and the number of edges m are given. Then m lines follow describing the edges, and subsequently a line provides the number k of critical rooms followed by the ids of these critical rooms. A dataset with n = 0 and m = 0 indicates the end of the input.

Mathematical Formulation:

For each dataset, if the list of critical rooms is represented by C and <(|C|) = k, then the answer is given by:

\( answer = k \)

inputFormat

The input is given via standard input (stdin) and consists of several datasets. Each dataset is formatted as follows:

  1. The first line contains two integers n (number of rooms) and m (number of edges).
  2. The next m lines each contain two integers u and v indicating an undirected edge between room u and room v.
  3. The following line starts with an integer k (the number of critical rooms), followed by k integers representing the ids of the critical rooms.

The input terminates with a line containing "0 0".

outputFormat

For each dataset, print the minimum number of isolation operations required (one integer per line) to isolate the critical rooms from the rest of the network.

## sample
5 4
1 2
2 3
3 4
4 5
2 2 4
3 3
1 2
2 3
1 3
1 1
0 0
2

1

</p>