1192 . 鑰匙設計
TopCoder
Tags
Description
我們想要做一隻長度為L(1<=L<=1,000,000)的萬能鑰匙。
所謂長度為L，是說這隻鑰匙從左到右總共L個刻度，而每個刻度上可以是凸的或凹的，而且它要能開n(1<=n<=1,000)種門。
這n種門, 每種門會有一組需求。
每組需求是:
插進去後由內往外數, 哪些刻度要是凹的, 哪些刻度要是凸的
每組需求最多只會有1,000個條件。(例如，我要求刻度1和刻度3必須是凹的，這就代表了兩個條件。)
沒有指定到的刻度則沒有限制。(對這個門孔來說)
此外，由於你必須使鑰匙至少有一部分露在外面(才拔得出來)，所有門孔的深度都不超過L/2。
刻度： １２３４５６７
鑰匙：▅▂▇▂▂▇▇▂▅
狀態： 凹凸凹凹凸凸凹
注意萬能鑰匙可以從兩個方向上使用(也就是說左右兩端都可以用來插門孔)，請參考上面的圖示自行想像_^
所以說是萬能鑰匙其實看起來是一根凹凹凸凸的棒子，不過這樣才能物盡其用, 兩面使用更為環保！
試問是否有辦法把這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
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
No
Hints
第一筆測試資料當中，把鑰匙打造成
刻度： １２３４５６７８９０
０９８７６５４３２１
鑰匙：▅▇▇▂▂▂▂▇▂▂▇▅
狀態： 凸凸凹凹凹凹凸凹凹凸
即可滿足一號門(從前面)，以及二、三號門(從後面)。
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 |