768 . 派對分組

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

50.0% (2/4)

Tags

apcsc apcsc-graph

Description

作為一個派對負責人，你想要舉辦兩場派對並邀請 N 個朋友到其中一場。每個朋友都對派對有所期待，他們一共提出 L 個派對應具備的特質，例如派對蛋糕上有沒有香菜。這些特質有些人贊成，也有些人反對，也有些人沒意見。你可以自由規劃派對，然而當有兩個人對某個特質意見互相衝突時 (一人贊成一人反對)，勢必會有一人感到不開心。想請問你是否能適當安排 N 個朋友到兩場派對的其中一場，使得同一場派對沒有兩個人有衝突意見？

Input Format

本題含多筆測試資料，第一行代表測試資料筆數 T。
每筆測試資料第一行是兩個空白分隔的正整數 N,L，分別代表朋友人數和派對特質數。
接著有 N 行每行有若干個空白分隔的整數，並恰有兩個 0，其中第二個 0 一定在結尾。
在第 i 行第一個 0 以前的正整數代表朋友 i 贊成的特質，第一個 0 以後第二個 0 以前的正整數是朋友 i 反對的特質。

輸入保證 T≤100，N≤1000，L≤106，派對特質編號 1∼L。假設 S 是總意見數，那麼保證 S≤105。

Output Format

對於每筆測試資料輸出一行，如果可以適當安排請輸出 Yes，否則輸出 No。

Sample Input 1

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

Sample Output 1

Yes
No

Hints

Problem Source

TIOJ 1192 鑰匙設計

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~11 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 2
2 3000 524288 65536 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
Submit
Back to Top