TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

88.1% (37/42)

Submission's AC Ratio

31.6% (68/215)

Tags

Description

我們想要做一隻長度為L(1<=L<=1,000,000)的萬能鑰匙。
所謂長度為L,是說這隻鑰匙從左到右總共L個刻度,而每個刻度上可以是凸的或凹的,而且它要能開n(1<=n<=1,000)種門。

這n種門, 每種門會有一組需求。

每組需求是:

插進去後由內往外數, 哪些刻度要是凹的, 哪些刻度要是凸的

每組需求最多只會有1,000個條件。(例如,我要求刻度1和刻度3必須是凹的,這就代表了兩個條件。)
沒有指定到的刻度則沒有限制。(對這個門孔來說)
此外,由於你必須使鑰匙至少有一部分露在外面(才拔得出來),所有門孔的深度都不超過L/2

   刻度: 1234567
   鑰匙:▅▂▇▂▂▇▇▂▅
   狀態: 凹凸凹凹凸凸凹

注意萬能鑰匙可以從兩個方向上使用(也就是說左右兩端都可以用來插門孔),請參考上面的圖示自行想像_^
所以說是萬能鑰匙其實看起來是一根凹凹凸凸的棒子,不過這樣才能物盡其用, 兩面使用更為環保!

試問是否有辦法把這n種鑰匙同時製造在這個萬能鑰匙上?

Input Format

輸入檔的第一列包含一個正整數T,代表測試資料的組數。
接下來有T筆測試資料,每筆測試資料的第一列有兩個正整數n,L。
然後有n列,每一列代表一個門所對應的鑰匙需求:首先是若干個正整數,代表需求為「凸」的刻度位置,然後以0做結束。接著又是若干個正整數,代表需求為「凹」的刻度位置,同樣以0做結束。
你可以假設輸入中所有的需求都是合理的。

Output Format

對於每一筆測試資料,若能夠打造一把同時能夠開啟所有n種門的鑰匙,請輸出Yes,否則請輸出No。

Sample Input 1

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

Sample Output 1

Yes
No

Hints

第一筆測試資料當中,把鑰匙打造成

   刻度: 1234567890
       0987654321
   鑰匙:▅▇▇▂▂▂▂▇▂▂▇▅
   狀態: 凸凸凹凹凹凹凸凹凹凸

即可滿足一號門(從前面),以及二、三號門(從後面)。

Problem Source

原TIOJ1192 / TIOJ 2008例行賽01-Elite (prob H)。Idea:Kelvin。

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5