| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 5 | 5 | 5 | 100.000% |
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?
Each problem's name consists of two words. Let's call two names similar if either their first words are the same or their second words are the same. For example, eight shaped and eight connected are similar, while hello world and world hello are not.
The 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.
You 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.
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.
The first line of each test case contains a single integer $n,ドル denoting the number of problems (2ドル \le n \le 10^5$).
The $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.
It is guaranteed that the sum of $n$ over all test cases does not exceed 10ドル^5$.
For each test case, print "Yes" if the judges followed the rule correctly, and "No" otherwise.
3 4 k shaped h shaped eight shaped eight connected 3 k shaped eight connected eight shaped 4 judging problem judging logic binary problem logic problem
Yes No Yes
In the first test case, each subsequent problem name is similar to the previous one.
In the second test case, the judges should have chosen "eight shaped" for the second year.
In the third test case, neither "binary problem" nor "logic problem" is similar to "judging logic"; the judges could have chosen either of those problems for the third year.