{"raw_statement":[{"iden":"problem statement","content":"There are $N$ slimes numbered from $1$ to $N$. The color of each slime is represented by an integer between $0$ and $2K$ (inclusive), and the color of slime $i$ is $C_i$.\nCurrently, $M$ pairs of slimes are in a (bidirectional) friendship. Specifically, slimes $A_i$ and $B_i$ are friends ($1 \\leq i \\leq M$). Here, it is guaranteed that for any two slimes, one can reach the other by following friendship relations.\nYou can perform the following operation:\n\n*   First, choose a pair of slimes $(u,v)$ that satisfies both of the following conditions:\n    *   Slimes $u$ and $v$ are in a friendship.\n    *   $(C_u - C_v) \\bmod (2K+1) \\geq K+1$ (here, the result of $x \\bmod y$ is always in the range $[0,y-1]$).\n*   Then, let slime $u$ eat slime $v$. Slime $v$ disappears from the field. Also, all slimes except $u$ that were in a friendship with slime $v$ become friends with slime $u$ (if they were already friends with slime $u$, nothing happens).\n\nDetermine whether it is possible to leave only slime $1$ on the field by repeating the operation appropriately.\nSolve $T$ cases for one input."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 125000$\n*   $2 \\leq N \\leq 250000$\n*   $N-1 \\leq M \\leq 250000$\n*   $1 \\leq K \\leq N$\n*   $0 \\leq C_i \\leq 2K$\n*   $1 \\leq A_i < B_i \\leq N$\n*   $(A_i,B_i) \\neq (A_j,B_j)$ ($i \\neq j$)\n*   For any two slimes, one can reach the other by following friendship relations.\n*   The sum of $N$ over the $T$ cases is at most $250000$.\n*   The sum of $M$ over the $T$ cases is at most $250000$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach test case is given in the following format:\n\n$N$ $M$ $K$\n$C_1$ $C_2$ $\\cdots$ $C_N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_M$ $B_M$"},{"iden":"sample input 1","content":"4\n2 1 1\n0 0\n1 2\n3 2 1\n0 2 1\n1 2\n2 3\n6 6 1\n0 0 1 2 1 0\n1 2\n2 3\n3 4\n4 5\n5 6\n1 6\n5 4 2\n2 4 3 2 1\n1 2\n2 4\n2 5\n3 5"},{"iden":"sample output 1","content":"No\nYes\nNo\nNo\n\nIn the first test case, no operation can be performed.\nIn the second test case, it is possible to leave only slime $1$ on the field by the following procedure:\n\n*   Choose $(u,v)=(3,2)$ and let slime $3$ eat slime $2$. Slime $2$ disappears, and slimes $1$ and $3$ become friends.\n*   Choose $(u,v)=(1,3)$ and let slime $1$ eat slime $3$. Slime $3$ disappears."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}