http://codeforces.com/contest/742/problem/E
跪着看題解後才會的。
對于任何一對BF[i]和GF[i]
連接配接了一條邊後，那麼他們和隔壁都是不會有邊相連的了，這是題目資料保證的。因為BF[i]和GF[i]是唯一确定的嘛。
那麼，我們把BF[i]連接配接去GF[i]的邊叫1類邊。
然後把2 * i - 1 和 2 * i也連上邊，是第二類邊。
那麼每個頂點的度數都是2，并且都是一條第一類邊和一條第二類的。
那麼如果有環，也是偶數環，不存在幾圈。是以直接染色即可。
hack:這個二分圖可能不是全部連接配接好的（就是有多個連通分量）。其實本來就不應該認為一定隻有一個連通分量。是以需要每個點都枚舉一次
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e6 + 20;
int first[maxn];
struct node {
int tonext;
int u, v;
}e[maxn];
int num;
int g[maxn];
int b[maxn];
int col[maxn];
void add(int u, int v) {
++num;
e[num].u = u;
e[num].v = v;
e[num].tonext = first[u];
first[u] = num;
}
bool vis[maxn];
int must[maxn];
void dfs(int cur, int which) {
col[cur] = which;
for (int i = first[cur]; i; i = e[i].tonext) {
int v = e[i].v;
if (vis[v]) {
// if (col[v] != !which) {
// cout << -1 << endl;
// exit(0);
// }
continue;
}
vis[v] = true;
dfs(v, !which);
}
}
void work() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int u, v;
scanf("%d%d", &u, &v);
b[i] = u;
g[i] = v;
add(u, v);
add(v, u);
}
for (int i = 1; i <= n; ++i) {
add(2 * i - 1, 2 * i);
add(2 * i, 2 * i - 1);
}
for (int i = 1; i <= 2 * n; ++i) {
if (vis[i]) continue;
vis[i] = true;
dfs(i, 0);
}
for (int i = 1; i <= n; ++i) {
printf("%d %d\n", col[b[i]] + 1, col[g[i]] + 1);
}
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return 0;
}