use proconio::input; use std::io::Write; fn main() { let mut writer = std::io::BufWriter::new(std::io::stdout().lock()); input! { t: usize } for _ in 0..t { let ans = if solve() { "Yes" } else { "No" }; writeln!(writer, "{ans}").unwrap(); } } fn solve() -> bool { input! { n: usize, mut pairs: [(String, String); n] } pairs.sort_unstable(); pairs.dedup(); let n = pairs.len(); let mut dsu = Dsu::new(2 * n + 1); let start = 2 * n; for i in 0..n { dsu.merge(i, n + i); if pairs[0].0.contains("a") { dsu.merge(i, start); } } for i in 0..n { for j in i..n { let yi = &pairs[i].1; let xj = &pairs[j].0; if yi.contains(xj) { if dsu.same(j, n + i) && dsu.same(j, start) { return true; } dsu.merge(j, n + i); } } } false } pub struct Dsu { parent_or_size: Vec, } impl Dsu { pub fn new(size: usize) -> Self { assert!(size <= i32::MAX as usize); Self { parent_or_size: vec![-1; size], } } pub fn clear(&mut self) { self.parent_or_size.fill(-1); } pub fn leader(&mut self, u: usize) -> usize { if self.parent_or_size[u] < 0 { return u; } self.parent_or_size[u] = self.leader(self.parent_or_size[u] as usize) as i32; self.parent_or_size[u] as usize } pub fn same(&mut self, u: usize, v: usize) -> bool { self.leader(u) == self.leader(v) } pub fn size(&mut self, u: usize) -> usize { let x = self.leader(u); -self.parent_or_size[x] as usize } pub fn merge(&mut self, u: usize, v: usize) -> usize { let (mut x, mut y) = (self.leader(u), self.leader(v)); if x == y { return x; } if self.size(x) < self.size(y) { std::mem::swap(&mut x, &mut y); } self.parent_or_size[x] += self.parent_or_size[y]; self.parent_or_size[y] = x as i32; x } pub fn groups(&mut self) -> Vec> { let n = self.parent_or_size.len(); let mut result = (0..n) .map(|u| { let size = if u == self.leader(u) { self.size(u) } else { 0 }; Vec::with_capacity(size) }) .collect::>(); for u in 0..n { result[self.leader(u)].push(u); } result.into_iter().filter(|v| !v.is_empty()).collect() } }