
ZOJ Problem Set  4116
There are $k$ people playing a game on a connected undirected simple graph with $n$ ($n \ge 2$) vertices (numbered from 0 to $(n1)$) and $m$ edges. These $k$ people, numbered from 0 to $(k1)$, are divided into two groups and the game goes as follows:
Given the initial graph when the game starts, if all people use the best strategy to win the game for their groups, which group will win the game? Recall that a simple graph is a graph with no self loops or multiple edges. InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains an integer $k$ ($2 \le k \le 10^5$), indicating the number of people. The second line contains a string $s_0s_1\dots s_{k1}$ of length $k$ ($s_i \in \{\text{'1'}, \text{'2'}\}$). $s_i = \text{'1'}$ indicates that person number $i$ belongs to the 1st group, and $s_i = \text{'2'}$ indicates that person number $i$ belongs to the 2nd group. The third line contains two integers $n$ and $m$ ($2 \le n \le 10^5$, $n1 \le m \le 10^5$), indicating the number of vertices and edges of the initial graph. The following $m$ lines each contains two integers $u_i$ and $v_i$ ($0 \le u_i, v_i < n$), indicating that there is an edge connecting vertex $u_i$ and $v_i$ in the initial graph. It's guaranteed that:
OutputFor each test case output one line containing one integer. If the 1st group wins, output "1" (without quotes); If the 2nd group wins, output "2" (without quotes). Sample Input3 5 11212 4 6 0 1 0 2 0 3 1 2 1 3 2 3 5 11121 5 7 0 2 1 3 2 4 0 3 1 2 3 2 4 1 3 121 4 3 0 1 0 2 1 3 Sample Output2 1 2 Author: CHEN, Shihan Source: The 10th Shandong Provincial Collegiate Programming Contest 