C. The Great Zebra Quest at ASZoo (Hard)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem; the only difference between the easy and hard versions is $$$k$$$ ($$$1 \le k \le n$$$)

Deep in the heart of the city lies ASZoo, a sprawling wildlife park known for its winding pathways, lush habitats, and the majestic herds of zebras in its savanna exhibit. As the annual Zebra Spotlight Festival approaches, the ASZoo team needs to map out the shortest route from every park corner to the nearest zebra enclosure, so visitors can dash off to see these striped wonders without getting lost.

In this problem, model the park as an undirected, unweighted, simple graph:

  • Nodes ($$$1$$$ through $$$N$$$): distinct locations in ASZoo—exhibit areas, rest stops, food kiosks, or pathway junctions.
  • Edges: bidirectional pathways connecting two locations; moving along an edge is one "step".

Among these locations, exactly $$$K$$$ contain zebra enclosures. For each location $$$i$$$, compute the minimum number of steps needed to reach any zebra enclosure. If $$$i$$$ itself has a zebra enclosure, its distance is $$$0$$$. If $$$i$$$ cannot reach any zebra enclosure, output $$$-1$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains 3 integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$), ($$$1 \le m \le min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2})$$$), ($$$1 \le k \le n$$$).

The next $$$m$$$ lines contains two integers, $$$u_i$$$, $$$v_i$$$ ($$$1 \le u, v \le n, u \neq v$$$), denots the edges. The $$${m + 2}^nd$$$ line contains $$$k$$$ integers ($$$ 1 \le a_i \le n$$$) denots the locations that contain zebra enclosures.

The sum of $$$n$$$, and $$$m$$$ doesn't exceed $$$2 \cdot 10^5$$$ over all test cases.

Output

For each test case, print a single line containing the following:

For each location from $$$1$$$ through $$$n$$$, print the minimum number of pathway steps required to reach any zebra enclosure.

Example
Input
1
5 5 1
1 2
2 3
3 4
4 5
5 1
1
Output
0 1 2 2 1