[Solution] Split Into Two Sets solution codeforces

Split Into Two Sets solution codeforces – Polycarp was recently given a set of 𝑛n (number 𝑛n — even) dominoes. Each domino contains two integers from 11 to 𝑛n.

Table of Contents

[Solution] Split Into Two Sets solution codeforces

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.

For example, if he has 44 dominoes: {1,4}{1,4}{1,3}{1,3}{3,2}{3,2} and {4,2}{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}{1,4} and {3,2}{3,2}), and the second set — the second and fourth ones ({1,3}{1,3} and {4,2}{4,2}).

Input

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains a single even integer 𝑛n (2𝑛21052≤n≤2⋅105) — the number of dominoes.

The next 𝑛n lines contain pairs of numbers 𝑎𝑖ai and 𝑏𝑖bi (1𝑎𝑖,𝑏𝑖𝑛1≤ai,bi≤n) describing the numbers on the 𝑖i-th domino.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105.

[Solution] Split Into Two Sets solution codeforces

For each test case print:

  • YES, if it is possible to divide 𝑛n dominoes into two sets so that the numbers on the dominoes of each set are different;
  • NO if this is not possible.

You can print YES and NO in any case (for example, the strings yEsyesYes and YES will be recognized as a positive answer).

Example
input

Copy
6
4
1 2
4 3
2 1
3 4
6
1 2
4 5
1 3
4 6
2 3
5 6
2
1 1
2 2
2
1 2
2 1
8
2 1
1 2
4 3
4 3
5 6
5 7
8 6
7 8
8
1 2
2 1
4 3
5 3
5 4
6 7
8 6
7 8
output

Copy
YES
NO
NO
YES
YES
NO

[Solution] Split Into Two Sets solution codeforces

In the first test case, the dominoes can be divided as follows:

  • First set of dominoes: [{1,2},{4,3}][{1,2},{4,3}]
  • Second set of dominoes: [{2,1},{3,4}][{2,1},{3,4}]

In other words, in the first set we take dominoes with numbers 11 and 22, and in the second set we take dominoes with numbers 33 and 44.In the second test case, there’s no way to divide dominoes into 22 sets, at least one of them will contain repeated number.

For Solution

Click Here

Leave a Comment