题目链接：http://codeforces.com/contest/742/problem/E
题意：
有一个环形的桌子，一共有n对情侣，2n个人，一共有两种菜。
现在让你输出一种方案，满足以下要求：
情侣间吃不同的菜
相邻的三个人不能都吃同一种菜
输出任意一个解：
先将相邻的两个人连边，这样就满足了3个人不吃同样一种菜。
情侣间连边。
图中就不存在奇数环。
那么就一定存在解。然后DFS染色就OK 了。
#include <bits/stdc++.h> using namespace std; const int maxn = *; vector <int> G[maxn];
int color[maxn];
int b[maxn];
int g[maxn]; bool dfs(int u)
{
for(int i=; i<G[u].size(); i++)
{
int v = G[u][i];
if(color[u]==color[v]) return false;
if(!color[v])
{
color[v] = - color[u];
if(!dfs(v)) return false;
}
}
return true;
} int main()
{
int n;
scanf("%d",&n); for(int i=; i<=n; i++)
{
G[i*-].push_back(*i);
G[i*].push_back(*i-);
} for(int i=; i<n; i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
b[i] = u;
g[i] = v;
} for(int i=; i<=*n; i++)
{
if(color[i]==)
{
color[i] = ;
dfs(i);
}
} for(int i=; i<n; i++)
{
printf("%d %d\n",color[b[i]],color[g[i]]);
}
return ;
}