HPU SummerDay22(河南理工大学暑期第二十二天)

今天讲了拓扑排序，相比较而言还是挺简单的，我觉得这也是BFS的应用。不得不说，BFS和DFS是真的太重要了，在图论里面。

Genealogical tree

Description:
The system of Martians' blood relations is confusing enough. Actually, Martians bud when they want and where they want. They gather together in different groups, so that a Martian can have one parent as well as ten. Nobody will be surprised by a hundred of children. Martians have got used to this and their style of life seems to them natural.
And in the Planetary Council the confusing genealogical system leads to some embarrassment. There meet the worthiest of Martians, and therefore in order to offend nobody in all of the discussions it is used first to give the floor to the old Martians, than to the younger ones and only than to the most young childless assessors. However, the maintenance of this order really is not a trivial task. Not always Martian knows all of his parents (and there's nothing to tell about his grandparents!). But if by a mistake first speak a grandson and only than his young appearing great-grandfather, this is a real scandal.
Your task is to write a program, which would define once and for all, an order that would guarantee that every member of the Council takes the floor earlier than each of his descendants.
Input

The first line of the standard input contains an only number N, 1 <= N <= 100 — a number of members of the Martian Planetary Council. According to the centuries-old tradition members of the Council are enumerated with the natural numbers from 1 up to N. Further, there are exactly N lines, moreover, the I-th line contains a list of I-th member's children. The list of children is a sequence of serial numbers of children in a arbitrary order separated by spaces. The list of children may be empty. The list (even if it is empty) ends with 0.

Output

The standard output should contain in its only line a sequence of speakers' numbers, separated by spaces. If several sequences satisfy the conditions of the problem, you are to write to the standard output any of them. At least one such sequence always exists.

Sample Input

5
0
4 5 1 0
1 0
5 3 0
3 0

Sample Output

2 4 5 3 1

Problem solving:
题意就是给你n个人，然后分别告诉你n个人后面有几个人，让你输出一种排列方式。

一开始没看懂题意WA了一次。

这道题就是拓扑排序的一道板子题。直接写就行了。

Code:

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;
int sijia[105];
vector<int> xiaozhu[105];
int main()
{
    int n,m,nn,mid;
    cin>>n;
    nn=n;
    for(int i=1;i<=n;i++)
    {
        while(cin>>m&&m)
        {
                sijia[m]++;
                xiaozhu[i].push_back(m);
                continue;
        }
    }
    queue<int> q;
    for(int i=1;i<=nn;i++)
    {
        if(sijia[i]==0)
        {
             q.push(i);
        }
    }
    while(!q.empty())
    {
        int qixi=q.front();
        q.pop();
        cout<<qixi<<" ";
        for(int i=0;i<xiaozhu[qixi].size();i++)
        {
            sijia[xiaozhu[qixi][i]]--;
            if(sijia[xiaozhu[qixi][i]]==0)
                q.push(xiaozhu[qixi][i]);
        }
    }
}

Window Pains

Description:
Boudreaux likes to multitask, especially when it comes to using his computer. Never satisfied with just running one application at a time, he usually runs nine applications, each in its own window. Due to limited screen real estate, he overlaps these windows and brings whatever window he currently needs to work with to the foreground. If his screen were a 4 x 4 grid of squares, each of Boudreaux's windows would be represented by the following 2 x 2 windows:

When Boudreaux brings a window to the foreground, all of its squares come to the top, overlapping any squares it shares with other windows. For example, if window 1 and then window 2 were brought to the foreground, the resulting representation would be:

Unfortunately, Boudreaux's computer is very unreliable and crashes often. He could easily tell if a crash occurred by looking at the windows and seeing a graphical representation that should not occur if windows were being brought to the foreground correctly. And this is where you come in . . .
Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.
A single data set has 3 components:
Start line - A single line:
START
Screen Shot - Four lines that represent the current graphical representation of the windows on Boudreaux's screen. Each position in this 4 x 4 matrix will represent the current piece of window showing in each square. To make input easier, the list of numbers on each line will be delimited by a single space.
End line - A single line:
END
After the last data set, there will be a single line:
ENDOFINPUT
Note that each piece of visible window will appear only in screen areas where the window could appear when brought to the front. For instance, a 1 can only appear in the top left quadrant.

Output

For each data set, there will be exactly one line of output. If there exists a sequence of bringing windows to the foreground that would result in the graphical representation of the windows on Boudreaux's screen, the output will be a single line with the statement:
THESE WINDOWS ARE CLEAN
Otherwise, the output will be a single line with the statement:
THESE WINDOWS ARE BROKEN

Sample Input

START
1 2 3 3
4 5 6 6
7 8 9 9
7 8 9 9
END
START
1 1 3 3
4 1 3 3
7 7 9 9
7 7 9 9
END
ENDOFINPUT

Sample Output

THESE WINDOWS ARE CLEAN
THESE WINDOWS ARE BROKEN

Problem solving:
这道题的题意有点恶心。而且也不太好想+好写。

这道题也是要用拓扑排序做的。反正我是绝对想不到的，先预处理，把4*4的矩阵初始化成这样的

这个我还是放大佬链接吧，自认为莫得能力讲清楚。。。
点这里进行传送：某学姐

Code:

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<cstring>
using namespace std;
int ma[10][10],sijia[10];
int dr[]={0,1,0,1},dc[]={0,0,1,1};
vector<int> ve[10][10];
bool solve()
{
    queue<int> q;
    for(int i=0;i<9;i++)
        if(sijia[i]==0) q.push(i);
    int sum=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int v=0;v<9;v++)
        {
            if(ma[u][v])
            {
                ma[u][v]=0;
                sijia[v]--;
                if(sijia[v]==0)   q.push(v);
            }
        }
        sum++;
    }
    return sum==9;
}
int main()
{
    for(int i=0;i<9;i++)
    {
        int r=i/3,c=i%3;
        for(int j=0;j<4;j++)
        {
            int nr=r+dr[j],nc=c+dc[j];
            ve[nr][nc].push_back(i);
        }
    }
    string s;
    while(cin>>s&&s[0]!='E')
    {
        memset(ma,0,sizeof(ma));
        memset(sijia,0,sizeof(sijia));
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                int v;
                cin>>v;
                v--;
                for(int k=0;k<ve[i][j].size();k++)
                {
                    if(ve[i][j][k]!=v)
                    {
                        int x=ve[i][j][k];
                        if(ma[x][v]==0)
                        {
                            sijia[v]++;
                            ma[x][v]=1;
                        }
                    }
                }
            }
        }
        if(solve()) puts("THESE WINDOWS ARE CLEAN");
        else    puts("THESE WINDOWS ARE BROKEN");
        cin>>s;
    }
}

确定比赛名次

Description:

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

Output

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。
其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

Sample Input

4 3
1 2
2 3
4 3

Sample Output

1 2 4 3

Problem solving:
给出n个队伍以及队伍的胜负关系，让你输出他们的排名。

也是一个简单的拓扑排序的板子题，注意以下输出，最后一个数后面没有空格，就行了。

Code:

#include<bits/stdc++.h>
using namespace std;
const int sijiaxiaozhu=521;
int qixikuaile[sijiaxiaozhu];
vector<int> yongyuan[sijiaxiaozhu];
int main()
{
  int n,m,x,y;
  while(cin>>n>>m)
  {
    memset(qixikuaile,0,sizeof(qixikuaile));
    for(int i=0;i<=n;i++) yongyuan[i].clear();
    for(int i=0;i<m;i++)
    {
      cin>>x>>y;
      qixikuaile[y]++;
      yongyuan[x].push_back(y);
    }

  priority_queue<int,vector<int>,greater<int> > q ;
    int flag=1;
    for(int i=1;i<=n;i++)
    {
      if(qixikuaile[i]==0)  q.push(i);
    }
    while(!q.empty())
    {
      int mid=q.top();
      q.pop();
      if(flag)
      {
        cout<<mid;
        flag=0;
      }
      else  cout<<" "<<mid;
      for(int i=0;i<yongyuan[mid].size();i++)
      {
        qixikuaile[yongyuan[mid][i]]--;
        if(qixikuaile[yongyuan[mid][i]]==0) q.push(yongyuan[mid][i]);
      }
    }
    cout<<endl;
  }
  return 0;
}

产生冠军

Description:
有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。
球赛的规则如下：
如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。
如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。
根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。
Input

输入含有一些选手群，每群选手都以一个整数n(n<1000)开头，后跟n对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示，前者战胜后者。如果n为0，则表示输入结束。

Output

对于每个选手群，若你判断出产生了冠军，则在一行中输出“Yes”，否则在一行中输出“No”。

Sample Input

3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0

Sample Output

Yes
No

Problem solving:
这道题跟上一题很像。也是给了你胜负关系，问你能不能确定冠军。但是胜负关系是通过字符串给出的。

想一下这就是可以用拓扑排序写，但是胜负关系是以字符串给出的，如果直接套我们的板子会发现一个很尴尬的问题，存图的时候字符串不可以做下标。但是这个时候可以用map给每个字符串赋一个值，然后套板子。讲道理，这个应该是可以实现的(虽然我没成功。

然后想一下，这道题可以这样做。确定冠军的话，就是有一个人一场都没输过。所以我们只需要比较出现的总人数以及输过的总人数的关系即可。如果差一个就说明有一个人一场都没输过。这就能确定冠军了。反之就不能。这样的话一个set就能解决了。

Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    string x,y;
    while(cin>>n&&n)
    {
        set<string> sijia;
        set<string> xiaozhu;
        for(int i=0;i<n;i++)
        {
            cin>>x>>y;
            sijia.insert(x),sijia.insert(y);
            xiaozhu.insert(y);
        }
            if(sijia.size()-xiaozhu.size()==1)  puts("Yes");
            else    puts("No");
    }
}

Legal or not

Description:
ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many "holy cows" like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost "master", and Lost will have a nice "prentice". By and by, there are many pairs of "master and prentice". But then problem occurs: there are too many masters and too many prentices, how can we know whether it is legal or not?

We all know a master can have many prentices and a prentice may have a lot of masters too, it's legal. Nevertheless，some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian's master and, at the same time, 3xian is HH's master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not.

Please note that the "master and prentice" relation is transitive. It means that if A is B's master ans B is C's master, then A is C's master.
Input

The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which means x is y's master and y is x's prentice. The input is terminated by N = 0.
TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,..., N-1). We use their numbers instead of their names.

Output

For each test case, print in one line the judgement of the messy relationship.
If it is legal, output "YES", otherwise "NO".

Sample Input

3 2
0 1
1 2
2 2
0 1
1 0
0 0

Sample Output

YES
NO

Problem solving:
题意就是告诉你n个关系，问你会不会产生矛盾。

一道拓扑排序的板子题，判断是否成环就行。

Code:

#include<bits/stdc++.h>
using namespace std;
int sijia[521];
vector<int> xiaozhu[521];
int main()
{
    int n,m,a,b;
    while(cin>>n>>m)
    {
        memset(sijia,0,sizeof(sijia));
        for(int i=0;i<=n;i++  )    xiaozhu[i].clear();
        if(n==0&&m==0)  break;
        for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            sijia[b]++;
            xiaozhu[a].push_back(b);
        }
        queue<int> q;
        for(int i=0;i<n;i++)
        {
            if(sijia[i]==0)
            q.push(i);
        }
        while(!q.empty())
        {
            int mid=q.front();
            q.pop();
            n--;
            for(int i=0;i<xiaozhu[mid].size();i++)
            {
                sijia[xiaozhu[mid][i]]--;
                if(sijia[xiaozhu[mid][i]]==0)
                    q.push(xiaozhu[mid][i]);
            }
        }
        if(n)   puts("NO");//如果n不为0，说明成环
        else    puts("YES");
    }
}

Reward

Description:
Dandelion's uncle is a boss of a factory. As the spring festival is coming , he wants to distribute rewards to his workers. Now he has a trouble about how to distribute the rewards.
The workers will compare their rewards ,and some one may have demands of the distributing of rewards ,just like a's reward should more than b's.Dandelion's unclue wants to fulfill all the demands, of course ,he wants to use the least money.Every work's reward will be at least 888 , because it's a lucky number.
Input

One line with two integers n and m ,stands for the number of works and the number of demands .(n<=10000,m<=20000)
then m lines ,each line contains two integers a and b ,stands for a's reward should be more than b's.

Output

For every case ,print the least money dandelion 's uncle needs to distribute .If it's impossible to fulfill all the works' demands ,print -1.

Sample Input

2 1
1 2
2 2
1 2
2 1

Sample Output

1777
-1

Problem solving:
这道题还是很有意思的，告诉你每个人的最低工资是888，然后给你大小关系，告诉你大小关系大于后者的工资也得比后者的多，问你老板做少需要支付多少工资。

虽然也是一道拓扑排序的板子题。但是中间的一些处理还是很难搞得。
我们把初始没经过处理的时候的入度为0的顶点的工资都设为888，然后在拓扑排序的过程中，送入队列的点的工资比他前一个加1就行，因为要求的是最少。
最后全布累加在一起，输出即可。

这道题还有一个坑点就是。存图的时候跟输出是反着来的。这个坑到我了。

注意还有输出-1的情况，就是出现了环的时候。

Code:

#include<bits/stdc++.h>
using namespace std;
#define maxn 10000
queue<int> q;
vector<int>t[10005];
int in[10005],sum[10005],cnt,u,v,ans;
void Init()   
{
    for(int i=0;i<maxn;i++)
      t[i].clear();
    while(!q.empty())
      q.pop();
    memset(in,0,sizeof(in));
    ans=0;
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        Init();
        for(int i=0;i<m;i++) 
        {
            cin>>u>>v;
            u--;v--;
            in[u]++;
            t[v].push_back(u);
        }
        for(int i=0;i<n;i++)
        {
            if(!in[i])
            {
                q.push(i);
                sum[i]=888;
            }
        }
        cnt=0;     
        while(!q.empty())
        {
            cnt++;    
            int p=q.front();
            q.pop();
            for(int i=0;i<t[p].size();i++)   
            {
                in[t[p][i]]--;    
                if(in[t[p][i]]==0)     
                {
                    q.push(t[p][i]);     
                    sum[t[p][i]]=sum[p]+1;    //对工资的处理
                }
            }
        }
        for(int i=0;i<n;i++)
          ans+=sum[i];
        if(cnt!=n)
          ans=-1;
        cout<<ans<<endl;
    }
    return 0;
}

Ordering Tasks

PDF题面:七夕快乐
Description:
John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is
only possible if other tasks have already been executed.
Input

The input will consist of several instances of the problem. Each instance begins with a line containing
two integers, 1 ≤ n ≤ 100 and m. n is the number of tasks (numbered from 1 to n) and m is the
number of direct precedence relations between tasks. After this, there will be m lines with two integers
i and j, representing the fact that task i must be executed before task j.
An instance with n = m = 0 will finish the input.

Output

For each instance, print a line with n integers representing the tasks in a possible order of execution.

Sample Input

5 4
1 2
2 3
1 3
1 5
0 0

Sample Output

1 4 2 5 3

Problem solving:
题意就是有n个工作，但是有的工作需要在另一个工作完成的基础上才能完成，问你一个合理的顺序。

拓扑排序板子题啦，输出就行。

Code:

#include<bits/stdc++.h>
using namespace std;
int sijia[105];
vector<int> xiaozhu[105];
int n,m,x,y;
int main()
{
    while(cin>>n>>m)
    {
        memset(sijia,0,sizeof(sijia));
        for(int i=0;i<=n;i++)   xiaozhu[i].clear();
        if(n==0&&m==0)  break;
        for(int i=0;i<m;i++)
        {
            cin>>x>>y;
            sijia[y]++;
            xiaozhu[x].push_back(y);
        }
        queue<int> qixi;
        for(int i=1;i<=n;i++)
        {
            if(sijia[i]==0) qixi.push(i);
        }
        while(!qixi.empty())
        {
            int kuaile=qixi.front();
            qixi.pop();
            cout<<kuaile<<" ";
            for(int i=0;i<xiaozhu[kuaile].size();i++)
            {
                sijia[xiaozhu[kuaile][i]]--;
                if(sijia[xiaozhu[kuaile][i]]==0)
                    qixi.push(xiaozhu[kuaile][i]);
            }
        }
        cout<<endl;
    }
}

Rank of Tetris

Description:
自从Lele开发了Rating系统，他的Tetris事业更是如虎添翼，不久他遍把这个游戏推向了全球。

为了更好的符合那些爱好者的喜好，Lele又想了一个新点子：他将制作一个全球Tetris高手排行榜，定时更新，名堂要比福布斯富豪榜还响。关于如何排名，这个不用说都知道是根据Rating从高到低来排，如果两个人具有相同的Rating，那就按这几个人的RP从高到低来排。

终于，Lele要开始行动了，对N个人进行排名。为了方便起见，每个人都已经被编号，分别从0到N-1,并且编号越大，RP就越高。
同时Lele从狗仔队里取得一些（M个）关于Rating的信息。这些信息可能有三种情况，分别是"A > B","A = B","A < B"，分别表示A的Rating高于B,等于B,小于B。

现在Lele并不是让你来帮他制作这个高手榜，他只是想知道，根据这些信息是否能够确定出这个高手榜，是的话就输出"OK"。否则就请你判断出错的原因，到底是因为信息不完全（输出"UNCERTAIN"），还是因为这些信息中包含冲突（输出"CONFLICT"）。
注意，如果信息中同时包含冲突且信息不完全，就输出"CONFLICT"。
Input

本题目包含多组测试，请处理到文件结束。
每组测试第一行包含两个整数N,M(0<=N<=10000,0<=M<=20000),分别表示要排名的人数以及得到的关系数。
接下来有M行，分别表示这些关系

Output

对于每组测试，在一行里按题目要求输出

Sample Input

3 3
0 > 1
1 < 2
0 > 2
4 4
1 = 2
1 > 3
2 > 0
0 > 1
3 3
1 > 0
1 > 2
2 < 1

Sample Output

OK
CONFLICT
UNCERTAIN

Problem solving:
题意就是告诉你n个人的rating大小关系。问你给的信息能否确定一个高手榜。如果信息不完全就输出UNCERTAIN，如果有冲突了就输出CONFLICT,如果可以就输出OK。并且如果rating相同的话，比较两个人的RP值，RP值的大小就是编号的大小。

如果只有大小关系的话，就是一个简单板子题，但是它这里还存在着一种等于的关系。这就很麻烦了。我们需要用到并查集来处理。只要出现等于号，就把那两个人join(合并函数)起来，放在一起处理。然后在存图的过程中如果是等于的关系直接跳过就行，否则就先找一下两个点的父节点，用父节点存图，这样就完美的解决了出现等号的情况——这点可能不是很清楚，自己在脑子里模拟一下想一下就可以了。接下来就是拓扑排序了。

再说一下三种输出。OK的话当然就是可以构建出来高手榜的时候输出，但是CONFLICT和UNCERTAIN有什么区别呢？

CONFLICT就是有了冲突，有了冲突是什么情况呢？就是存的图里面出现了有环存在的情况，也就是最后还有入度不为0的结点存在。
UNCERTAIN就是不确定，不确定是什么情况呢？就是有两个节点的大小关系不知道，也就是存着入度为0的节点的队列中存在两个以上的节点，这个应该还挺好理解的，如果在同一次循环中出现了两个入度为0的节点，说明这两个点之间没有任何边连接着，所以他俩的大小关系自然是不确定了。

到这里我们发现并没有处理rating相同然后比较RP的问题，这是为什么呢？
因为如果出现了等于关系，那么按照题意来说我们应该比较两者的RP值，但是RP值得大小关系是和和编号的大小一样的，而编号每个人都是不一样的，所以就算出现了相等的情况，在不考虑别的情况下一定能比较出大小。所以不需要考虑这个问题。

Code:

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
int n,m,sijia[52121],p[52121],sum;
vector<int> ma[52121];
struct node{
    int x,y;
    char s;
}xiaozhu[52121];
int find(int x)
{
    return p[x]!=x?p[x]=find(p[x]):x;//并查集的查找函数
}
bool join(int x,int y)//并查集的合并函数，这里设置成bool类型是为了下面方便
{
    x=find(x),y=find(y);
    if(x==y)//如果x和y的父节点已经相等了，就不用在处理了
        return 0;
    p[x]=y;
    return 1;
}
void solve()//拓扑排序
{
    queue<int> q;
    for(int i=0;i<n;i++)
    {
        if(p[i]==i&&sijia[i]==0)    q.push(i);
    }
    int flag=0;
    while(!q.empty())
    {
        if(q.size()>1)  flag=1;   //入度为0的点同时出现了两个
        int mid=q.front();
        q.pop();sum--;
        for(int i=0;i<ma[mid].size();i++)
        {
            sijia[ma[mid][i]]--;
            if(sijia[ma[mid][i]]==0)    q.push(ma[mid][i]);
        }
    }
    if(sum>0)   puts("CONFLICT");  //有环存在
    else if(flag)   puts("UNCERTAIN");//sum大于0说明同一等级上不是只有唯一的一个
    else    puts("OK");
}
int main()
{
    while(cin>>n>>m)
    {
        memset(sijia,0,sizeof(sijia));
        memset(ma,0,sizeof(ma));
        sum=n;
        for(int i=0;i<n;i++)    p[i]=i;
        for(int i=0;i<m;i++)
        {
            cin>>xiaozhu[i].x>>xiaozhu[i].s>>xiaozhu[i].y;
            if(xiaozhu[i].s=='=')//如果出现了等号，就把两个合并
            {
                if(join(xiaozhu[i].x,xiaozhu[i].y))
                {
                    sum--;//因为合并起来了两个，所以总的拓扑排序用到的节点数减一
                }
            }
        }
        for(int i=0;i<m;i++)//存图
        {
            if(xiaozhu[i].s=='=')   continue;
            int xx=find(xiaozhu[i].x),yy=find(xiaozhu[i].y);
            if(xiaozhu[i].s=='>')
            {
                ma[xx].push_back(yy);
                sijia[yy]++;
            }
            else
            {
                ma[yy].push_back(xx);
                sijia[xx]++;
            }
        }
        solve();
    }
}