http://codeforces.com/contest/782/problem/D
题意：
每个队有两种队名，问有没有满足以下两个条件的命名方法：
①任意两个队的名字不相同。
②若某个队 A 选用了第二种队名，那么如果队 B 的第一种队名和队 A 的相同，那么同样不能选择。当然，队B的第二个队名无所谓
思路：
学习了2-sat发现这题这么简单= =。
如果那天A了这题就前200了
//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
/*
另第一个名字为a，第二个名字为b
一：
如果ai = aj，那么只能选择第二个
①如果bi = bj，那么无解
②如果bi != bj，那么两者之间连接一条边
上面是分类讨论 二：
如果ai != aj */
const int maxn = + ;
struct TwoSAT{
int n;
vector<int> G[maxn * ];
bool mark[maxn * ];
int c, s[maxn * ];///c是表示目前dfs到的个数和已经被标记的集合s
bool dfs(int x){
if (mark[x ^ ]) return false;
if (mark[x]) return true;
mark[x] = true;
s[c++] = x;
for (int i = ; i < G[x].size(); i++)
if (!dfs(G[x][i])) return false;
return true;
} void init(int n){
this->n = n;
for (int i = ; i < * n; i++) G[i].clear();
memset(mark, , sizeof(mark));
}
///利用题目条件找到x和y，即假设x1[0] | x2[1] = false;即：x1[0]|!x2[1]=false
///那么我们反转该条件：即x1[1]|!x2[0] = true,即两者任意一个成立即为true
///那么我们只要交叉建图即可
void addedge(int x, int y){
G[x].pb(y);
} bool solve(){
for (int i = ; i < * n; i += ){
if (!mark[i] && !mark[i + ]){
c = ;
if (!dfs(i)){
while (c) mark[s[--c]] = false;
if (!dfs(i + )) return false;
}
}
}
return true;
}
};
TwoSAT tar;
int n;
pair<string, string> p[maxn];
char a[], b[]; bool solve(){
for (int i = ; i < n; i++){
for (int j = i + ; j < n; j++){
if (p[i].fi == p[j].fi){
if (p[i].se == p[j].se) return false;
else
tar.addedge(i*, i*+), tar.addedge(j*, j*+);
}
else {
if (p[i].fi == p[j].se){
tar.addedge(i*, j*), tar.addedge(j*+, i*+);
}
if (p[i].se == p[j].fi){
tar.addedge(i*+, j*+), tar.addedge(j*, i*);
}
if (p[i].se == p[j].se){
tar.addedge(i*+, j*), tar.addedge(j*+, i*);
}
}
}
}
if (!tar.solve()) return false;
puts("YES");
for (int i = ; i < * n; i += ){
if (tar.mark[i]){
cout << p[i/].fi << endl;
}
else {
cout << p[i/].se << endl;
}
}
return true;
} int main(){
cin >> n;
tar.init(n);
for (int i = ; i < n; i++){
scanf("%s%s", a, b);
p[i].fi = p[i].fi + a[] + a[] + a[];
p[i].se = p[i].se + a[] + a[] + b[];
}
if (!solve()) puts("NO");
return ;
}