ITAI Virus

Interview

Time limit1sMemory limit256 MB

Summary

Count the initially infected cities plus every city directly joined to one by a single road.

Level: Easy2 of 10
Topics: Graph, Implementation
Solved: No attempts yet

Problem

Insane Transferable Abnormal Illness, ITAI for short, is a viral disease first found in the southern part of a city. A person who catches the virus screams "Itai, itai!" without stopping.

When the virus appears in a city it splits in two and travels along every road that touches that city. The city it started from keeps the virus as well. The ITAI virus is weak: once it reaches another city it degenerates into a weak virus that never spreads again.

A country has $N$ cities, numbered 1 to $N$ , and $M$ roads. The Ministry of Health inspected the country and found the virus in $K$ cities. Every one of those $K$ cities holds a new virus that can still spread.

Find how many cities hold the virus after all of the spreading is over.

Input

The first line has the number of test cases $T$ . ( $1 \le T \le 10$ )

Each test case is given in the following format.

The first line has the number of cities $N$ , the number of roads $M$ , and the number of cities where the virus was found $K$ . ( $1 \le N \le 1000$ , $1 \le M \le 2N$ , $0 \le K \le N$ )
The next $M$ lines each have two integers $A$ and $B$ describing a road. ( $1 \le A \le N$ , $1 \le B \le N$ ) The road connects city $A$ and city $B$ in both directions. Several roads may connect the same pair of cities, and $A$ may equal $B$ .
The next line has the $K$ numbers of the cities where the virus was found. If $K$ is 0, this line is empty.

Output

For each test case, print the number of cities that hold the virus on its own line.

Hint

The cities that hold the virus are the cities where the virus was found together with the cities joined to them by a single road. A city that can only be reached by crossing two or more roads stays clean.

Examples2

Example 1

Input

Expected output

2
4
4

Example 2

Input

10
4 4 3
2 2
4 3
1 2
2 3
3 4 2
1 1 1
1 1
1
1 1 0
1 1

7 2 0
5 3
7 5

2 1 0
2 1

4 6 0
4 3
1 3
4 4
2 2
2 3
1 3

9 12 8
2 6
6 2
2 1
8 2
8 5
3 3
2 3
9 6
9 1
1 2
8 3
4 6
9 6 2 1 4 3 7 5
1 2 1
1 1
1 1
1
3 3 2
2 3
1 2
3 2
3 2
12 1 9
4 5
9 2 1 7 10 11 3 8 6

Expected output