5303: I love playing games
内存限制：256 MB
时间限制：15.000 S
评测方式：文本比较
命题人：
提交：5
解决：0
题目描述
Alice and Bob play a game on an undirected graph G consisting of n vertices numbered 1 to n, and m edges.
Before the game starts, Alice is at vertex x, Bob is at vertex y. The game rules as follows:
* Alice goes first, then Bob. with moves alternating each turn.
* They try to get the vertex z. At the end of a turn, if Alice arrives but Bob does not, Alice wins; If Bob arrives but Alice does not, Bob wins; If both arrive or both fail to arrive, it will be considered a draw.
* In a move, the current player can choose not to move or move to a vertex adjacent to the current vertex, if there is an edge between the two vertex.
* The player cannot be on the same vertex at the same time except the start position and end position.
* Both of them play in the optimal way. (i.e If there is a strategy to win, win; if not, try to get to a draw)
Your task is to determine who wins if both of them choose the best operation in their rounds.
Before the game starts, Alice is at vertex x, Bob is at vertex y. The game rules as follows:
* Alice goes first, then Bob. with moves alternating each turn.
* They try to get the vertex z. At the end of a turn, if Alice arrives but Bob does not, Alice wins; If Bob arrives but Alice does not, Bob wins; If both arrive or both fail to arrive, it will be considered a draw.
* In a move, the current pla
* The pla
* Both of them play in the optimal way. (i.e If there is a strategy to win, win; if not, try to get to a draw)
Your task is to determine who wins if both of them choose the best operation in their rounds.
输入
There is only one test case for this question.
The first line contains an integer T(T<=10000) . Then T test cases follow.
Each test case contains m+2 lines.
The first line contains two integers n and m (n≤103) — numbers of vertices and edges in graph respectively.
The second line contains three integers x,y and z — the initial position of Alice,the initial position of Bob and the end position of them.
The next m lines contain edges descriptions. Each line contains two integers x and y (1≤x≤n,1≤y≤n)— denoting that there is an undirected edge between the vertices numbered x and y.
It is guaranteed that the sum of n over all test cases doesn't exceed 105 and the sum of m over all test cases doesn't exceed 2∗105. The given graph may contain loops and multi-edges.
The first line contains an integer T(T<=10000) . Then T test cases follow.
Each test case contains m+2 lines.
The first line contains two integers n and m (n≤103) — numbers of vertices and edges in graph respectively.
The second line contains three integers x,y and z — the initial position of Alice,the initial position of Bob and the end position of them.
The next m lines contain edges desc
It is guaranteed that the sum of n over all test cases doesn't exceed 105 and the sum of m over all test cases doesn't exceed 2∗105. The given graph may contain loops and multi-edges.
输出
Print T integer, for each case, determine who wins. Output
* an integer 1 if Alice wins.
* an integer 2 if draw. i.e no one wins.
* an integer 3 if Bob wins.
* an integer 1 if Alice wins.
* an integer 2 if draw. i.e no one wins.
* an integer 3 if Bob wins.
样例输入 复制
2
10 13
8 1 10
1 2
1 3
2 4
2 5
3 5
8 9
9 4
9 5
4 6
5 6
6 10
5 7
7 10
8 9
2 3 8
1 2
2 6
2 7
6 4
7 5
4 3
5 3
6 8
7 8样例输出 复制
1
1