题 目 连 接

这个构造建图有点难捏~

分析一下：
首先我们规定图中的边的性质：边的两个端点不能吃同一种食物；

对于情侣：每对情侣之间建边；
对于相邻3个人：我们可以对相邻的两个人建边（不妨让2*i-1 和 2*i建边），这样相邻三个人就不会吃同一种了；

这样建完的图没有奇数环：
具体看这里：https://blog.csdn.net/weixin_45630722/article/details/120188980

注意一个性质：一个图是二分图 <=> 这个图中没有奇数环(奇数环：环中边的数量是奇数)

因此这个图是个二分图；

然后由于食物只有两种，我们直接对二分图染色就行；
（写的时候一直在想这两种食物要怎么分配...其实这个不是重点...）

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<cmath> 
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;

#define pb push_back
#define coutt cout<<"------------"<<endl;
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> PII;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;

const int maxn = 1e6 + 7;
const int N = 2e5+7;
const int M = 1e6+7;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = 3.14159265359;

ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}

int h[maxn],e[maxn],ne[maxn],idx;
int vis[maxn];
PII p[maxn];    //情侣

void add(int a,int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

bool dfs(int u,int c)
{
    vis[u] = c; //染色

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(!vis[j]) //这个点没被染色过
        {
            if(!dfs(j,3-c)) return false;   //出现矛盾返回false
        }
        else if(vis[j] == c) return false;//这个点被染过色 而且 颜色相同，矛盾
    }

    return true;    
}

int main()
{
    memset(h,-1,sizeof h);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++)   //情侣建边
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
        p[i] = {a,b};
    }

    for(int i=1;i<=n;i++)   //相邻建边
    {
        add(2*i-1,2*i);
        add(2*i,2*i-1);
    }

    int f = 1;
    for(int i=1;i<=2*n;i++)
        if(!vis[i])
        {
            if(!dfs(i,1))
            {
                f = 0;
                break;
            }
        }

    if(!f) cout<<"-1"<<endl;
    else
    {
        for(int i=1;i<=n;i++) cout<<vis[p[i].first]<<' '<<vis[p[i].second]<<endl;
    }

    return 0;   
}