405721: GYM102055 H Game on the Tree

Mr. Panda and Mr. Sheep are playing a game on a connected undirected graph with $$$N$$$ vertices and $$$N$$$ edges. Initially, Mr. Panda and Mr. Sheep stand on two distinct vertices $$$A$$$ and $$$B$$$ of the graph. The game plays in turns with Mr. Panda plays first. Each turn, a player can either stay where he/she is or move to an adjacent vertex. Mr. Panda can only move to vertices that are not visited by Mr. Sheep.

Some vertices are marked as destinations. The game ends when Mr. Panda reaches any destination vertex and Mr. Panda wins.

Please help Mr. Panda to answer whether he can win the game, assuming both players play optimally.

The first line of the input gives the number of test cases, $$$T$$$ ($$$1 \le T \le 20$$$). $$$T$$$ test cases follow.

Each test case contains one integer, $$$N$$$ ($$$1 \leq N \leq 2 \times 10^5$$$), where $$$N$$$ is the number of vertices and edges of the graph.

The following $$$N$$$ lines each contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x \neq y \le N$$$), indicating there is an edge between vertex $$$x$$$ and vertex $$$y$$$.

The following line contains an integer $$$M$$$ ($$$1 \leq M \leq N$$$), the number of destinations, followed by a line containing $$$M$$$ distinct integers: $$$v_1, v_2, \ldots, v_M$$$ ($$$1 \le v_i \le N$$$).

The last line contains two integers $$$A$$$ and $$$B$$$ ($$$1 \le A \neq B \le N$$$), where $$$A$$$ is the starting vertex of Mr. Panda and $$$B$$$ is the starting vertex of Mr. Sheep.

For each test case, output "Case x:" first, where x is the test case number (starting from $$$1$$$). If Mr. Panda can win the game, output "Panda"; otherwise (draw or lose) output "Sheep".

2
5
1 2
2 3
3 4
4 5
5 2
1
3
1 5
5
1 2
2 3
3 4
4 5
5 3
1
3
1 5

Case 1: Panda
Case 2: Sheep