问题 G: vvvvvvvim

问题 G: vvvvvvvim

时间限制: 3 Sec  内存限制: 512 MB
提交: 10  解决: 1
[状态] [讨论版] [提交] [命题人:]
题目描述
一天,心血来潮的 Toxel 对 vim 进行了魔改。他在 vim 中添加了指令 vvvvvvv,该指令可以在一段文本中选取任意一条连续的路径进行操作。Toxel 将这一全新的文本编辑器命名为 vvvvvvvim。
vvvvvvvim 中的一段文本包含若干行,每行包含若干个从行首开头的字符,与一般的文本编辑器相同。第 i 行左起的第 j 个字符用坐标 (i,j) 表示(i,j 均从 1 开始)。
vvvvvvv 指令选取的连续路径可定义为从文本中某个存在的字符开始,每次向上、下、左、右移动一个字符,通过有限次移动得到的字符序列。移动的过程中不允许走到不存在字符的位置,但可以重复访问同一位置的字符。
形式化地说,vvvvvvv 指令选取的路径可表示为 (x1,y1)→(x2,y2)→⋯→(xt,yt)(t≥1),其中 t 表示路径长度。设 n 表示文本行数,那么要求对于所有的 i(1≤i≤t) 满足 1≤xi≤n,1≤yi≤lenxi。并且对于所有的 i(1≤i<t) 满足 ∣xi−xi+1∣+∣yi−yi+1∣=1。
为了测试你对 vvvvvvvim 的掌握情况,Toxel 给了你两段文本,它们的行数相同,所有对应行的长度也相同。你需要在第一段文本上使用 vvvvvvvim 指令选取一条路径,将路径上所有字符统一修改成字符 ch(ch 可任选),使得两段文本相同。请判断是否可行。两段文本相同是指行数相同,每行的长度相同,且所有对应位置的字符也相同。


输入
注意:本题包含多组测试数据。
第一行包含一个整数 T (1≤T≤5×105),表示数据组数。接下来依次给出 T 组测试数据。
每组测试数据的第一行包含一个整数 n,表示两段文本的行数均为 n (1≤n≤5×105)。
接下来 n 行描述第一段文本的内容。输入的第 i 行包含一个字符串 c1t1c2t2⋯cdtd,表示文本的第 i 行有 d 段,依次为 t1 个 c1,t2 个 c2,以此类推。字符与数字间没有空格,参见样例。保证所有 cj 均为小写字母,tj 为整数且 1≤tj≤109,1≤d≤5×105,∑j=1dtj≤109
接下来 n 行描述第二段文本的内容,格式和限制与第一段文本相同。保证两段文本所有对应行的长度相同。
保证单个测试点中所有测试数据第一段文本的 d 之和不超过 5×105,第二段文本的 d 之和不超过 5×105
输出
对于每组测试数据,输出一行一个字符串,Yes 表示可以修改第一段文本使得两段文本相同,No 表示不能,大小写不敏感。
样例输入 Copy
1
2
a2
a1b1
b2
b2
样例输出 Copy
Yes
提示
样例输入二
1
1
a1b1a1
b1a1a1
样例输出二
No
第一个样例中,第一段文本为:
aa
ab
第二段文本为:
bb
bb
可以选择从第一行的第二个字符开始,走到第一行的第一个字符,再走到第二行的第一个字符。将路径选中的这些字符全部修改为字符 b 后,两段文本就相同了。
第二个样例则没有办法只使用一次操作来完成目标。