codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.