(the most detailed in History) codeforces round 805 (Div. 3) e Split Into Two Sets

One . The question

Here you are. n Double sided dominoes , There is a number on each side （ This number is in 1~n Within the scope of ）, Your goal is to divide these dominoes into two piles , So that the numbers on each side of each pile of dominoes are not the same , That is, each pile does not contain the same number .

Two . The tools used

Union checking set

3、 ... and . Ideas

If it can be divided into two piles, it must have the following properties ：

1. The front and back of each domino are different .

2. Every number must appear 2 Time （ Suppose a number appears less than 2 Time , Because there are 2*n A digital （ The number range is 1~n Between ）, Then there must be other numbers more than 2 Time , Then it must not be divided into two piles so that this number appears in two piles and only once ）

3. If you connect all the numbers that appear in a domino at the same time , Then eventually it will be formed by one or more rings （ Undirected graph Ring in the sense ）.

（ The reason for the ring formation ： Because every number will appear twice , So every numerical degree is 2, Therefore, the properties of rings are satisfied ）

such as

1 2

2 1

3 4

4 3

In the end, it will form a 1-2（ Middle two-way side ） Ring and one 3-4 （ Middle two-way side ） Ring

Another example

1 2

2 3

3 1

In the end, it will form a 1-2-3-1 Ring

4. If it can be divided into two piles , Then all the rings formed （ Every connected block ） in , Are even rings （ The number of sides is even , There are even numbers in it ）.

4 The proof of ： First of all, I want to emphasize again that if there are two numbers on the edge in the graph, there is a domino composed of these two numbers .

Similar to dyeing , If we want to divide into two groups, let's take logarithm on the interval of the ring

Interval is to put two adjacent numbers into a heap , The next two are placed in different piles , I don't know how to take a look at the following simulation

（ If you don't do this, you can take one pile at a time and then change to the next one , The same number is bound to appear in a pile   for example 1-2-3-1 Ring If you don't take it at intervals, take it for the first time from left to right 1-2 Put the first pile   Take... For the second time 2-3 Put the first pile   2 Will repeat ）

There is also a specific classification retrieval process , The text description ends with a picture .

eg

You can draw such an odd ring , Then use boxes and rings to represent 1 Group and 2 Group , Draw a frame on the ring .

Here is a picture , You can combine text introduction with pictures to see ！

Odd number （ The number of sides is odd , In this ring The types of numbers are also odd ） Ring 1-2-3-1   

Put the first pile  1-2

Put the second pile 2-3

Put the first pile 3-1

Finally, it must be repeated , Because in the end 1 Set up a circle 2-3 Box and 1 Set up a circle 4-2 The boxes of have intersections .

But even numbers （ The number of sides is even , In this ring The number category is also even ） Ring won't

for example ：1-2-3-4-1

Put the first pile 1-2

Put the second pile  2-3

Put the first pile 3-4

Put the second pile 4-1

In this way, all circles are finished ！ And there is no intersection with ,□ and □ There's no intersection , That is, the same number will not appear in the same pile ！

Left is an example of odd rings , The right is an example of an even ring

How can we achieve it ？

In this way, each card consists of one or more rings with two numbers connected , Each ring is actually a connected block , So we just saw When the number type in a connected block is an odd number, it is not ok , Even numbers are ok , So we can use the union search set with size , Because each connected block of the joint search set can only store one number of each kind, right , Therefore, the size of each connected block in the union search set is even （ There are even numbers in a ring ） You can share , At least one connected block number is odd （ There are odd numbers in a ring ） You can't divide .

Four . Code implementation

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;
const int N = 2e5+10;
map<int,int> cnt,cntab;
int f[N];
int find(int a)
{
    if(a!=f[a]) f[a]=find(f[a]);
    return f[a];
}
void merge(int a,int b)
{
    int fa=find(a);
    int fb=find(b);
    if(fa!=fb)
    {
        f[fb]=fa;
        cnt[fa]+=cnt[fb];
    }
    
}
void solve()
{
    int n;
    cin>>n;
    cnt.clear(),cntab.clear();
    for(int i=1;i<=n;i++) f[i]=i,cnt[i]=1;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        merge(a,b);
        cntab[a]++,cntab[b]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(cntab[i]!=2)// Conditions 2
        {
            puts("NO");
            return;
        }
        if(f[i]==i)
        {
            if(cnt[i]&1)// Conditions 4
            {
                puts("NO");
                return;
            }
        }
    }
    puts("YES");
    
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
}