Playing Connection Woods

2 secs 1024 MB
matcharate12's icon matcharate12

問題

クリスマスの翌日。クリスマスの日の楽しい思い出を呼び起こすために、matchababy君はリビングにある暖炉のそばで、数字が書かれた横長の木材で遊んでいるようです。木材は NN 個あり、i (1iN)i\ (1\le i\le N) 個目の木材には LiL_i 個の整数 A(i,1),A(i,2),A(i,Li)A_{(i,1)},A_{(i,2)},…A_{(i,L_i)} が書かれていました。

これらの木材を任意の順番に並べ替え、N1N-1 本の糸を使って全ての木材をつなげて、繋がった木材に書かれた数を左から順に並べて数列 AA を作ります。AA を広義単調増加となるように並べることができるような木材の繋ぎ方は存在しますか?
ただし木材は回転して繋げても良いですが、木材単体を切り離してはいけないものとします。

入力・制約

NN
L1 A(1,1)  A(1,L1)L_1\ A_{(1,1)}\ …\ A_{(1,L_1)}
L2 A(2,1)  A(2,L2)L_2\ A_{(2,1)}\ …\ A_{(2,L_2)}
\vdots
LN A(N,1)  A(N,LN)L_N\ A_{(N,1)}\ …\ A_{(N,L_N)}

2N25002\le N\le 2500
1Li1 \le L_i
i=1NLi104\displaystyle\sum^N_{i=1}L_i\le 10^4
・全ての i,j (1jLi)i,j\ (1\le j\le L_i) に対し 1A(i,j)1091 \le A_{(i,j)}\le 10^9
・全ての ii に対し A(i,1)<A(i,2)<<A(i,Li)A_{(i,1)}\lt A_{(i,2)}\lt …\lt A_{(i,L_i)} または A(i,1)>A(i,2)>>A(i,Li)A_{(i,1)}\gt A_{(i,2)}\gt …\gt A_{(i,L_i)}

出力

問題の条件を満たす繋ぎ方が存在するなら Yes 、しないなら No を出力せよ。

入出力例

入力例1
4
2 1 2
2 5 6
2 7 8
2 3 4
出力例1
Yes

(1,2),(3,4),(5,6),(7,8)(1,2),(3,4),(5,6),(7,8) と書かれた木材をこの順につなげることで達成できます。

入力例2
3
3 3 4 5
1 4
2 2 3
出力例2
No

どう並び替えても達成できません。

入力例3
4
3 1 7 10
2 11 12
2 14 15
2 14 13
出力例3
Yes

(1,7,10),(11,12),(13,14),(14,15)(1,7,10),(11,12),(13,14),(14,15) の順に並べて繋げることで達成できます。木材は回転して並べることができることに注意して下さい。

提出


Go (1.21)