| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14372 | 2024_DS_Summer_Lab14_How far is the closest cookie |
|
Description
A Takodachi is a creature which loves cookies.
There is a Takodachi on an undirected graph G = (V, E). There are cookies on the graph, given in a set S. Your job is to tell the Takodachi the distance between it and the closest reachable cookie. If there is no cookie reachable for the Takodachi, it becomes sad. Print "SAD" in capital for it.
Note that:
- G may not be connected.
- G doesn't have multiple edges and self-loops.
- It is possible that there is no cookie within reach of the Takodachi.
- A cookie is reachable if there exist a path between the vertex where the Takodachi is on and the cookie.
Input
The first line of the input contains T — the number of testcases.
The first line of each testcase contains two integers n and m — the size of V and the size of E.
Then m lines follow, each line contains two integers ui and vi , being an edge in E.
The next line contains s, the index of the vertex where the Takodachi is.
The next line is |S|, the size of the set S.
Following by the set S itself, denoting which vertices have cookies on, each vertex of the set is seperated by a space.
Output
For each testcase, print the minimum distant to the closest cookie. If the Takodachi cannot reach any cookie, print "SAD" in capital.