题目描述：

有n对情侣（2n个人）围成一圈坐在桌子边上，每个人占据一个位子，要求情侣不能吃同一
种食物，并且桌子上相邻的三个人的食物必须有两个人是不同的，只有两种食物（1或者是2），问一种可行分配方式。

题解：

如果我们能把不能吃同一种食物的人连边，问题就变成二分图黑白染***r>• 所以情侣关系等价于两者之间连一条边
• “每连续的三个人不能都一样”怎么办？
• 让第2i个人和第2i+1个人不能吃一样的食物即可（即1连2，3连4，5连6以此类推）
• 这样肯定是个二分图——2i和2i-1分别连了他两的情侣，情侣又分别连他两的一个邻居……
每次都是给这个可能存在的环加两个点，所以有环就一定不是奇环

在这里插入图片描述
蓝边表示情侣连边，红边表示相邻点对隔一对连一条
基础的二分图问题

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
const int maxn=5e5+9;
vector<int>edge[maxn];
int a[maxn];
int b[maxn];
int col[maxn];
int vis[maxn];
void dfs(int now,int co)
{
    vis[now]=1;
    col[now]=co;
    for(int i:edge[now])
    {
        if(!vis[i])
        {
            if(co==1)
                dfs(i,2);
            else 
                dfs(i,1);    
        }
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        edge[a[i]].push_back(b[i]);
        edge[b[i]].push_back(a[i]); 
    }
    for(int i=1;i<=n*2;i=i+2)
    {
        edge[i].push_back(i+1);
        edge[i+1].push_back(i);
    }
    for(int i=1;i<=2*n;i++)
    {
        if(!vis[i])dfs(i,1);
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d %d\n",col[a[i]],col[b[i]]);
    }
    return 0;
}