from collections import deque class AhoCorasick: def __init__(self): self.next = [dict()] self.fail = [0] self.out = [[]] 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([]) 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]]) 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) 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")