from collections import deque class AhoCorasick: def __init__(self): self.next = [dict()] self.fail = [0] self.out = [[]] self.out_link = [0] def add(self, pattern: str, pattern_id: int) -> None: v = 0 for ch in pattern: if ch not in self.next[v]: new_node = len(self.next) self.next[v][ch] = new_node self.next.append(dict()) self.fail.append(0) self.out.append([]) self.out_link.append(0) v = self.next[v][ch] self.out[v].append(pattern_id) def build(self) -> None: q = deque() for ch, u in self.next[0].items(): self.fail[u] = 0 q.append(u) while q: v = q.popleft() # 以前はここで self.out[v].extend(self.out[self.fail[v]]) として、 # fail 先で見つかるパターンを out[v] にコピーしていました。 # しかしコピーすると同じ pattern_id が多くのノードに複製され、MLE の原因になります。 # そこで out_link[v] に「fail をたどった先で、次に out があるノード」を覚えます。 if self.out[self.fail[v]]: self.out_link[v] = self.fail[v] else: self.out_link[v] = self.out_link[self.fail[v]] for ch, u in self.next[v].items(): f = self.fail[v] while f != 0 and ch not in self.next[f]: f = self.fail[f] if ch in self.next[f]: self.fail[u] = self.next[f][ch] else: self.fail[u] = 0 q.append(u) def search(self, text: str, on_match) -> None: v = 0 for pos, ch in enumerate(text): while v != 0 and ch not in self.next[v]: v = self.fail[v] if ch in self.next[v]: v = self.next[v][ch] else: v = 0 for pattern_id in self.out[v]: # 見つかった結果をリストにためず、その場で呼び出し側に渡します。 # この問題では「どの位置で見つかったか」は不要なので、 # pattern_id だけを渡せば十分です。 on_match(pattern_id) # out_link をたどると、fail 先にあるパターンも見つけられます。 # 例: "she" に到達したとき、out_link で "he" のノードへ進めば、 # "she" の末尾にある "he" も検出できます。 # out をコピーしていないので、メモリを増やさずに同じ判定ができます。 u = self.out_link[v] while u != 0: for pattern_id in self.out[u]: on_match(pattern_id) u = self.out_link[u] T = int(input()) for _ in range(T): N = int(input()) patterns = [] texts = [] for _ in range(N): x,y = input().split() patterns.append(x) texts.append(y) if "a" not in patterns: print("No") else: ac = AhoCorasick() for i,p in enumerate(patterns): ac.add(p, i) ac.build() G = [set() for _ in range(N)] for i,t in enumerate(texts): # ac.search(t, G[i].add) と書くと、 # X_j が Y_i の中で見つかるたびに G[i].add(j) がすぐ実行されます。 # G[i] は set なので、同じ j が何度見つかっても 1 回だけ保存されます。 ac.search(t, G[i].add) que = deque() A = set() for i,pattern in enumerate(patterns): if pattern == "a": que.append(i) A.add(i) while que: u = que.popleft() for v in G[u]: if v not in A: A.add(v) que.append(v) F = {i:[] for i in range(N)} B = {i:0 for i in A} for i in A: for v in G[i]: if v in A: F[i].append(v) B[v] += 1 que = deque() for v in B: if B[v] == 0: que.append(v) while que: u = que.popleft() for v in F[u]: B[v] -= 1 if B[v] == 0: que.append(v) flag = 0 for v in B: flag += B[v] if flag==0: print("No") else: print("Yes")