Labyrinth Challenge

You are given a series of datasets representing a labyrinth described as an undirected graph. Each dataset contains the following:

• An integer \(n\): the number of chambers.
• An integer \(m\): the number of direct connections between chambers.
• An integer \(B\): the battery units available.
• An initial chamber, \(c_1\).
• A sequence of target chambers to visit in order.
• A list of \(m\) bidirectional connections between chambers.

The robot starts at chamber \(c_1\) and must visit all the target chambers in the given order. The robot uses one unit of battery per unit of distance traveled. The distance between any two chambers is defined as the minimum number of connections required to travel from one to the other. If any target is unreachable or the total distance exceeds the battery capacity \(B\), the answer is Impossible; otherwise, it is Possible.

Note: If \(n = 0\), the labyrinth is considered invalid and the output should be Impossible.

inputFormat

The input is read from standard input and has the following format:

T
// Number of datasets
For each dataset:
n m B
c1
k t1 t2 ... tk
a1 b1
a2 b2
...
am bm

</p>

Here, the first line contains an integer \(T\) indicating the number of datasets. For each dataset:

• The first line contains three space-separated integers: \(n\), \(m\), and \(B\).
• The second line contains the initial chamber \(c_1\).
• The third line begins with an integer \(k\) representing the number of target chambers, followed by \(k\) space-separated integers representing the target chambers.
• The next \(m\) lines each contain two space-separated integers representing a bidirectional connection between two chambers.

outputFormat

For each dataset, output a single line with either Possible or Impossible (without quotes) to indicate whether the robot can complete its journey with the given battery constraint.

## sample

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

Possible
Possible
Impossible
Impossible
Impossible

</p>