P3234 [HNOI2014] Copying Decklists

One day, a bored Xiao L started playing the currently popular game Hearthstone, but he kept losing. He shouted, “I’m going to copy a decklist!” and went to watch the livestream of top Legend player Xiao H. However, Xiao L’s internet is still stuck in the dial-up era. The livestream is laggy and garbled, and his poor connection makes it impossible to record the full powerful decklist Xiao H shows. No one around Xiao L plays games, but they are all top students who love discussing informatics problems. So he came up with an idea: since each garbled frame appears in different positions on the screen, Xiao L can record some parts of the decklist each time. If he records many times, maybe he can reconstruct a decklist Xiao L wants. But there’s a problem: the decklist Xiao H shows each time might be different. So he wants to know whether the decklist fragments he copied each time are consistent. Abstracted as an academic problem for you to solve: the wildcard `*` matches a string of any length (including $0$). Determine whether all the strings are pairwise matching.

The first line contains a positive integer $T$, the number of test cases. Then follow $T$ test cases: For each test case, the first line contains a positive integer $N$, the number of strings in this test case. Then follow $N$ lines, each containing one string. Each string consists only of lowercase letters, digits, and the wildcard symbol `*`. Note: The testdata is in UNIX format and may contain blank lines. You may read the input character by character.

Output $T$ lines, each containing a single letter `Y` or `N`. `Y` means all strings in this test case are pairwise matching, and `N` means there exists at least one pair of strings that do not match.

For $100\%$ of the testdata, $N \leq 100000$, $T = 10$, the input file size does not exceed $10\text{M}$, and $N \times$ the longest string length does not exceed $2 \times 10^8$. Currently, only in hack testdata, $T = 1$. Translated by ChatGPT 5