2388 . 沒梗題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

93.3% (14/15)

Submission's AC Ratio

55.8% (53/95)

Tags

CKsim 2024-CKsim

Description

給你一張 $n$ 點 $m$ 邊的簡單無向連通圖跟一個陣列 $c_i$，請問：能不能把每個點塗成黑色或白色，使得對於每個點來說，他的鄰居（有連邊的點）中黑色的數量和$c_i$奇偶性相同？

Input Format

第一行有兩個正整數 $n,m$ ，意義如題目所述
第二行有$n$個正整數 $c_i$ ，意義如題目所述
接下來的 $m$ 行每行有兩個正整數 $u_i,v_i$ ，表示有一條邊$(u_i,v_i)$

對於所有測試資料：

  • $1 \leq n\leq 2000$
  • $1 \leq m\leq 100000$
  • $0\leq c_i \leq 1$
  • $ 1\leq u_i,v_i \leq n$

Output Format

可以達成則輸出"Yes"，否則輸出"No"。

Sample Input 1

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

Sample Output 1

Yes

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~5 $n\leq 20$ 13
3 0~10 $n\leq 500$ 27
4 0~21 無特別限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 3 4
1 1000 65536 65536 2 3 4
2 1000 65536 65536 2 3 4
3 1000 65536 65536 2 3 4
4 1000 65536 65536 2 3 4
5 1000 65536 65536 2 3 4
6 1000 65536 65536 3 4
7 1000 65536 65536 3 4
8 1000 65536 65536 3 4
9 1000 65536 65536 3 4
10 1000 65536 65536 3 4
11 1000 65536 65536 4
12 1000 65536 65536 4
13 1000 65536 65536 4
14 1000 65536 65536 4
15 1000 65536 65536 4
16 1000 65536 65536 4
17 1000 65536 65536 4
18 1000 65536 65536 4
19 1000 65536 65536 4
20 1000 65536 65536 4
21 1000 65536 65536 4
Submit
Back to Top