[Solution] Split Into Two Sets Codeforces Solution

E. Split Into Two Sets

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp was recently given a set of n$n$ (number n$n$ — even) dominoes. Each domino contains two integers from 1$1$ to n$n$.

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 4$4$ 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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 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$t$ (1≤t≤104$1\le t\le {10}^4$) — 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$n$ (2≤n≤2⋅105$2\le n\le 2\cdot {10}^5$) — the number of dominoes.

YES or YES? Codeforces Solution

ICPC Balloons Codeforces Solution

Cypher Codeforces Solution

Double Strings CodeForces Solution

Mirror Grid Codeforces Solution

Yet Another Problem About Pairs Satisfying an Inequality Codeforces Solution

Good Key, Bad Key Codeforces Solution

The next n$n$ lines contain pairs of numbers ai$a_i$ and bi$b_i$ (1≤ai,bi≤n$1\le a_i,b_i\le n$) describing the numbers on the i$i$-th domino.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case print:

• YES, if it is possible to divide n$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 yEs, yes, Yes and YES will be recognized as a positive answer).