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()) x_to_id = {} ys_by_x = [] for _ in range(N): x,y = input().split() # 同じ X を持つルールは、同じグラフノードとして扱います。 # 例: X が "a" のルールが 100 個あっても、ノードは 1 個だけ作ります。 if x not in x_to_id: x_to_id[x] = len(x_to_id) ys_by_x.append([]) ys_by_x[x_to_id[x]].append(y) if "a" not in x_to_id: print("No") else: M = len(x_to_id) ac = AhoCorasick() # Aho-Corasick に入れる X も、重複を除いたものだけにします。 # pattern_id は「元のルール番号」ではなく「X のグループ番号」です。 for x, group_id in x_to_id.items(): ac.add(x, group_id) ac.build() G = [[] for _ in range(M)] for i, y_list in enumerate(ys_by_x): seen = set() def add_edge(j): # 同じ X グループ i から同じ X グループ j への辺は 1 本あれば十分です。 # i に対応する複数の Y の中で j が何度見つかっても、重複して保存しません。 if j not in seen: seen.add(j) G[i].append(j) # 同じ X を持つ複数のルールは、すべて同じ出発ノード i からの選択肢です。 # それぞれの Y に含まれる X グループを探し、辺 i -> j を作ります。 for y in y_list: ac.search(y, add_edge) que = deque() A = set() start = x_to_id["a"] que.append(start) A.add(start) while que: u = que.popleft() for v in G[u]: if v not in A: A.add(v) que.append(v) B = {i:0 for i in A} for i in A: for v in G[i]: if v in A: B[v] += 1 que = deque() for v in B: if B[v] == 0: que.append(v) while que: u = que.popleft() for v in G[u]: if v in A: 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")