{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThere 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:\n\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003eThey 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.\u003c/li\u003e\n \u003cli\u003eDuring 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.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003eGiven 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?\u003c/p\u003e\n\n\u003cp\u003eRecall that a simple graph is a graph with no self loops or multiple edges.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains an integer $k$ ($2 \\le k \\le 10^5$), indicating the number of people.\u003c/p\u003e\n\n\u003cp\u003eThe second line contains a string $s_0s_1\\dots s_{k-1}$ of length $k$ ($s_i \\in \\{\\text{\u00271\u0027}, \\text{\u00272\u0027}\\}$). $s_i \u003d \\text{\u00271\u0027}$ indicates that person number $i$ belongs to the 1st group, and $s_i \u003d \\text{\u00272\u0027}$ indicates that person number $i$ belongs to the 2nd group.\u003c/p\u003e\n\n\u003cp\u003eThe 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.\u003c/p\u003e\n\n\u003cp\u003eThe following $m$ lines each contains two integers $u_i$ and $v_i$ ($0 \\le u_i, v_i \u0026lt; n$), indicating that there is an edge connecting vertex $u_i$ and $v_i$ in the initial graph.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that:\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003eThe initial graph is a connected undirected simple graph.\u003c/li\u003e\n \u003cli\u003eThere exist two people who belong to different groups.\u003c/li\u003e\n \u003cli\u003eThe sum of $k$, the sum of $n$ and the sum of $m$ in all test cases will not exceed $10^6$.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor 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).\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n5\n11212\n4 6\n0 1\n0 2\n0 3\n1 2\n1 3\n2 3\n5\n11121\n5 7\n0 2\n1 3\n2 4\n0 3\n1 2\n3 2\n4 1\n3\n121\n4 3\n0 1\n0 2\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}