1702E.md (2307B)
1 Source: https://codeforces.com/problemset/problem/1702/E 2 3 E. Split Into Two Sets 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Polycarp was recently given a set of $n$ (number $n$ — even) dominoes. Each domino contains two integers from $1$ to $n$. 22 23 Can he divide all the dominoes into two sets so that all the numbers on the dominoes of each set are different? Each domino must go into exactly one of the two sets. 24 25 For example, if he has $4$ dominoes: $\{1, 4\}$, $\{1, 3\}$, $\{3, 2\}$ and $\{4, 2\}$, then Polycarp will be able to divide them into two sets in the required way. The first set can include the first and third dominoes ($\{1, 4\}$ and $\{3, 2\}$), and the second set — the second and fourth ones ($\{1, 3\}$ and $\{4, 2\}$). 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 The descriptions of the test cases follow. 32 33 The first line of each test case contains a single even integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of dominoes. 34 35 The next $n$ lines contain pairs of numbers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) describing the numbers on the $i$-th domino. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case print: 42 43 * YES, if it is possible to divide $n$ dominoes into two sets so that the numbers on the dominoes of each set are different; 44 * NO if this is not possible. 45 46 You can print YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive answer). 47 48 Example 49 50 Input 51 52 ``` 53 6 54 55 4 56 57 1 2 58 59 4 3 60 61 2 1 62 63 3 4 64 65 6 66 67 1 2 68 69 4 5 70 71 1 3 72 73 4 6 74 75 2 3 76 77 5 6 78 79 2 80 81 1 1 82 83 2 2 84 85 2 86 87 1 2 88 89 2 1 90 91 8 92 93 2 1 94 95 1 2 96 97 4 3 98 99 4 3 100 101 5 6 102 103 5 7 104 105 8 6 106 107 7 8 108 109 8 110 111 1 2 112 113 2 1 114 115 4 3 116 117 5 3 118 119 5 4 120 121 6 7 122 123 8 6 124 125 7 8 126 ``` 127 128 Output 129 130 ``` 131 YES 132 NO 133 NO 134 YES 135 YES 136 NO 137 ``` 138 139 Note 140 141 In the first test case, the dominoes can be divided as follows: 142 143 * First set of dominoes: $[\{1, 2\}, \{4, 3\}]$ 144 * Second set of dominoes: $[\{2, 1\}, \{3, 4\}]$ 145 146 In other words, in the first set we take dominoes with numbers $1$ and $2$, and in the second set we take dominoes with numbers $3$ and $4$. 147 148 In the second test case, there's no way to divide dominoes into $2$ sets, at least one of them will contain repeated number.