{"extraResources":{"example.01.mu":"TVXzATMNCiFjMTs0DQprIHNoYXBlZA0KaCBzaGFwZWQNCmVpZ2h0IHNoYXBlZA0KZWlnaHQgY29ubmVjdGVkDQohYzI7Mw0KayBzaGFwZWQNCmVpZ2h0IGNvbm5lY3RlZA0KZWlnaHQgc2hhcGVkDQohYzM7NA0KanVkZ2luZyBwcm9ibGVtDQpqdWRnaW5nIGxvZ2ljDQpiaW5hcnkgcHJvYmxlbQ0KbG9naWMgcHJvYmxlbQ0K","example.01.a.mu":"TVXzASFjMTtZZXMNCiFjMjtObw0KIWMzO1llcw0K"},"scoring":null,"notes":"In the first test case, each subsequent problem name is similar to the previous one.\r\n\r\nIn the second test case, the judges should have chosen ``\\t{eight shaped}'' for the second year.\r\n\r\nIn the third test case, neither ``\\t{binary problem}'' nor ``\\t{logic problem}'' is similar to ``\\t{judging logic}''; the judges could have chosen either of those problems for the third year.","legend":"The judges of NWRRC came up with $n$ problems on a similar topic and decided to use them for $n$ consecutive years, one problem per year. The only question was: in what order should they be used?\r\n\r\nEach problem's name consists of two words. Let's call two names \\textit{similar} if either their first words are the same or their second words are the same. For example, \\texttt{eight shaped} and \\texttt{eight connected} are similar, while \\texttt{hello world} and \\texttt{world hello} are not.\r\n\r\nThe judges decided to implement the following rule: in the first year, they chose a problem arbitrarily. In~every subsequent year, if there was a problem with a name similar to the previous year's problem that was still unused, they chose one of such problems; otherwise, they chose any unused problem.\r\n\r\nYou are given the names of the problems in chronological order of their use. Determine whether the judges correctly followed the rule above, or if they made a mistake.","authorLogin":"tourist","language":"english","timeLimit":2000,"output":"For each test case, print ``\\t{Yes}'' if the judges followed the rule correctly, and ``\\t{No}'' otherwise.","inputFile":"stdin","outputFile":"stdout","input":"Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \\le t \\le 10^4$). The description of the test cases follows.\r\n\r\nThe first line of each test case contains a single integer $n$, denoting the number of problems ($2 \\le n \\le 10^5$).\r\n\r\nThe $i$-th of the following $n$ lines contains the name of the $i$-th problem in chronological order: two words consisting of at least $1$ and at most $10$ lowercase English letters each. All problem names are distinct.\r\n\r\nIt is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.","authorName":"Gennady Korotkevich","sampleTests":[{"output":"Yes\r\nNo\r\nYes\r\n","input":"3\r\n4\r\nk shaped\r\nh shaped\r\neight shaped\r\neight connected\r\n3\r\nk shaped\r\neight connected\r\neight shaped\r\n4\r\njudging problem\r\njudging logic\r\nbinary problem\r\nlogic problem\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"Judging Problem","interaction":null,"memoryLimit":1073741824,"tutorial":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Захар Яковлев, Геннадий Короткевич \\\\\r\n         Разработка: & Никита Голиков \\\\\r\n     \\end{tabular}\r\n}\r\n\r\n\r\nРассмотрим две задачи, выбранные в годы $i$ и $i + 1$. Если их названия похожи, то при выборе названия в год $i+1$ правило было выполнено.\r\n\r\nВ противном случае необходимо проверить, что на суффиксе, начинающемся с $i+1$, нет задач, похожих на $i$-ю. Для этого пройдем по задачам в обратном порядке, начиная с $n$-й. Во время итерации мы будем хранить два множества слов: одно множество будет хранить все использованные первые слова в суффиксе, а другое~--- все использованные вторые слова.\r\n\r\nПри проверке задачи $i+1$, если названия $i$-й и $(i+1)$-й не были похожи, мы проверим, содержит ли какое-либо из множеств соответствующее слово из $i$-го названия. Если какое-либо из множеств содержит это слово, это означает, что правило не было соблюдено в год $i+1$.\r\n\r\nЕсли все проверки прошли успешно, это означает, что судьи правильно следовали правилу. Время работы решения $O(n)$ или $O(n \\log n)$, в зависимости от реализации используемой структуры данных множества."}