F. Game on a Graph
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$k$$$ people playing a game on a connected undirected simple graph with $$$n$$$ ($$$n \ge 2$$$) vertices (numbered from 0 to $$$(n-1)$$$) and $$$m$$$ edges. These $$$k$$$ people, numbered from 0 to $$$(k-1)$$$, are divided into two groups and the game goes as follows:

  • They take turns to make the move. That is to say, person number 0 will make the 1st move, person number 1 will make the 2nd move, ..., person number $$$(i \mod k)$$$ will make the $$$(i+1)$$$-th move.
  • During a move, the current player MUST select an edge from the current graph and remove it. If the graph is no longer connected after removing the edge, the group this person belongs to loses the game (and of course their opponents win), and the game ends immediately.

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.

Input

There 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_{k-1}$$$ 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$$$, $$$n-1 \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 \lt n$$$), indicating that there is an edge connecting vertex $$$u_i$$$ and $$$v_i$$$ in the initial graph.

It's guaranteed that:

  • The initial graph is a connected undirected simple graph.
  • There exist two people who belong to different groups.
  • The sum of $$$k$$$, the sum of $$$n$$$ and the sum of $$$m$$$ in all test cases will not exceed $$$10^6$$$.
Output

For 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).

Example
Input
3
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
Output
2
1
2