Slime Eat Slime

AtCoder

IDagc076_c

Time3000ms

Memory256MB

Difficulty—

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$. Currently, $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. You can perform the following operation: * First, choose a pair of slimes $(u,v)$ that satisfies both of the following conditions: * Slimes $u$ and $v$ are in a friendship. * $(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]$). * 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). Determine whether it is possible to leave only slime $1$ on the field by repeating the operation appropriately. Solve $T$ cases for one input. ## Constraints * $1 \leq T \leq 125000$ * $2 \leq N \leq 250000$ * $N-1 \leq M \leq 250000$ * $1 \leq K \leq N$ * $0 \leq C_i \leq 2K$ * $1 \leq A_i < B_i \leq N$ * $(A_i,B_i) \neq (A_j,B_j)$ ($i \neq j$) * For any two slimes, one can reach the other by following friendship relations. * The sum of $N$ over the $T$ cases is at most $250000$. * The sum of $M$ over the $T$ cases is at most $250000$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $case_1$ $case_2$ $\vdots$ $case_T$ Each test case is given in the following format: $N$ $M$ $K$ $C_1$ $C_2$ $\cdots$ $C_N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$ [samples]

Samples

Input #1

4
2 1 1
0 0
1 2
3 2 1
0 2 1
1 2
2 3
6 6 1
0 0 1 2 1 0
1 2
2 3
3 4
4 5
5 6
1 6
5 4 2
2 4 3 2 1
1 2
2 4
2 5
3 5

Output #1

No
Yes
No
No

In the first test case, no operation can be performed.
In the second test case, it is possible to leave only slime $1$ on the field by the following procedure:

*   Choose $(u,v)=(3,2)$ and let slime $3$ eat slime $2$. Slime $2$ disappears, and slimes $1$ and $3$ become friends.
*   Choose $(u,v)=(1,3)$ and let slime $1$ eat slime $3$. Slime $3$ disappears.

API Response (JSON)

{
  "problem": {
    "name": "Slime Eat Slime",
    "description": {
      "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$. Currently, $M$ pairs of slime",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc076_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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 slime...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments