The Shannon switching game is a two-player game invented by Claude Shannon, the ``father of information theory'' sometime before 1951. In the game, two players take turns choosing and removing the edges of an arbitrary graph. One player aims to connect two distinguished vertices by a path of edges chosen by him/her. The other player aims to prevent this. The formal definition is as follows:
Given an undirected graph
possibly with multiple edges and two vertices
. Two players Join Player and Cut Player take turns doing the following operation, starting from Cut Player:
- Choose an edge
, and remove the edge
from
.
The game ends when either player cannot make a valid move, and the winner of the game is determined as follows:
- If the set of edges chosen by Join Player connects
and
, then Join Player wins. - Otherwise, Cut Player wins.
Alfred Lehman solved this problem in 1964 in a paper named
A Solution of the Shannon Switching Game. Lehman observed that the structure of this game is intimately related to a combinatorial structure named
matroid and presented a solution based on the property of matroids.
Recently, when gispzjz came across this problem, he understood the original problem and the solution immediately and invented the following variant of the game:
Given an undirected graph
possibly with multiple edges and two vertices
. There is a token initially placed at
. Two players Join Player and Cut Player take turns doing the following operation, starting from Cut Player:
- If it is Join Player's turn, assuming the token is currently at vertex
, Join Player can choose an incident edge
, remove the edge
from
and move the token to vertex
; - If it is Cut Player's turn, assuming the token is currently at vertex
, Cut Player can choose an incident edge
and remove the edge
from
.
The game ends when either player cannot make a valid move, and the winner of the game is determined as follows:
- If the token ever reaches
during the game, then Join Player wins. - Otherwise, Cut Player wins.
gispzjz quickly came up with a solution for determining the winner of the game under the optimal strategy of both players, but the solution can't fit on the rest of the page. Can you help him write the solution down?
输入描述:
The first line of input contains an integer
, denoting the number of test cases.
For each test case, the first line of the input contains four integers
, denoting the number of vertices and edges in the graph, the given starting vertex and ending vertex, respectively.
Then
lines follow, with each line containing two integers
, denoting an edge
in the graph. Note that there may be multiple edges in the graph but not self loops.
输出描述:
For each test case, if Join Player wins under optimal strategy of both players, output "Join Player"(without quotes) in a line, otherwise output "Cut Player"(without quotes) in a line .
示例1
输入
复制
3
2 1 1 2
1 2
2 2 1 2
1 2
1 2
3 3 1 2
1 2
2 3
1 3
输出
复制
Cut Player
Join Player
Cut Player
备注:
In the first test case of the sample test, Cut Player can remove the only edge and win the game.
In the second test case, no matter which edge Cut Player picks, Join Player can choose the remaining edge and move the token to vertex
, thus winning the game.
In the third test case, Cut Player can remove the edge
, then Join Player is only allowed to choose edge
and move the token to vertex
, then Cut Player can remove the edge
and win the game.