Code: Select all
3
1
2
3
4
5
6
3
A
1
2
1
2
3
3
A
2
2
1
D
1
Code: Select all
6
4
5
A
4
5
B
6
7
4
5
6
7
Code: Select all
YES
4 A
5 B
6 B
7 B
Code: Select all
NO
Code: Select all
7
3
D
4
C
B
6
9
C
4
4
A
D
D
C
5
7
5
B
4
D
2
A
5
B
3
6
C
A
C
C
6
D
3
5
5
B
B
8
4
B
7
3
1
D
1
1
8
9
B
C
B
A
9
B
A
5
D
D
4
2
6
D
A
A
B
5
7
A
B
C
B
1
2
2
A
3
A
7
C
8
B
7
D
3
1
3
3
5
2
6
D
C
6
7
C
4
10
A
9
9
B
A
6
5
2
5
9
C
B
5
A
7
C
4
C
5
2
7
7
C
8
1
C
B
D
B
7
6
3
B
B
D
6
6
A
B
6
3
8
D
C
D
9
D
B
3
6
C
B
8
7
2
1
A
7
1
1
C
2
5
2
4
6
6
1
C
1
B
4
B
D
A
B
2
2
D
1
4
B
8
3
2
B
5
2
B
A
2
9
9
C
5
C
C
A
A
10
1
B
1
C
A
7
9
D
B
1
2
C
2
6
A
D
7
1
7
3
2
9
D
C
B
6
B
2
C
2
7
B
D
1
C
C
2
3
1
6
D
8
3
8
7
5
C
A
A
7
7
3
C
A
7
4
2
A
10
A
D
7
9
A
9
4
9
C
D
B
5
A
A
8
B
8
6
A
B
8
B
B
B
6
C
A
7
1
8
9
9
2
9
9
B
2
9
B
3
5
2
C
3
6
2
C
B
4
A
5
C
5
6
C
B
9
D
5
A
1
2
3
9
7
A
8
A
4
A
7
B
1
1
B
9
A
2
A
6
9
B
D
9
D
8
C
4
2
9
B
5
5
B
9
4
6
D
A
5
D
C
D
9
C
5
B
C
D
1
C
5
4
2
1
D
1
7
5
3
D
4
D
C
2
1
D
5
C
3
C
C
B
C
D
7
10
B
3
1
C
3
3
4
9
C
B
D
A
B
A
A
A
A
B
A
5
10
5
B
7
7
6
A
4
B
3
4
B
D
1
7
C
B
6
5
8
A
7
A
4
C
D
5
7
B
C
D
D
2
7
D
B
9
B
A
1
A
A
6
9
D
B
B
6
B
9
3
B
5
D
B
2
4
9
B
B
7
D
8
8
8
B
3
5
A
1
5
B
9
3
B
3
B
C
D
4
6
D
8
B
C
2
1
D
B
D
5
5
C
5
B
D
D
C
9
1
A
5
3
2
D
C
D
2
C
2
B
D
C
7
4
A
B
2
D
D
A
1
7
8
B
6
2
4
B
2
D
1
D
4
1
5
4
2
B
A
9
B
D
C
8
5
9
1
C
5
6
C
C
6
D
1
3
3
D
2
2
5
C
3
8
2
9
C
B
2
5
3
8
C
A
B
7
A
D
A
8
3
7
9
B
2
D
C
6
D
B
6
4
D
C
2
9
D
5
B
A
8
5
B
3
3
5
D
C
2
A
4
1
9
C
3
8
A
3
9
4
B
D
A
2
3
A
4
A
5
8
6
6
3
6
D
D
5
1
B
A
3
A
A
D
3
B
D
5
D
D
5
1
A
8
6
5
5
D
C
3
B
6
D
D
4
3
C
8
B
A
6
5
1
B
B
C
9
7
A
7
6
2
4
7
6
A
9
2
A
5
B
D
6
9
A
B
6
9
D
2
A
3
4
B
6
1
3
D
C
C
D
6
C
C
B
A
4
D
C
9
5
C
A
B
2
3
1
4
3
B
9
D
8
1
8
D
C
3
7
3
A
2
D
B
2
5
B
6
7
8
3
B
3
9
A
8
B
C
9
2
B
9
2
C
C
9
8
D
A
D
B
B
3
4
2
7
9
2
D
1
2
5
D
5
6
D
4
6
7
3
D
D
7
B
5
8
9
A
5
A
4
6
A
A
C
1
6
3
8
7
D
B
4
8
5
D
2
6
7
D
A
6
4
4
C
5
1
A
A
7
4
A
8
5
3
8
7
6
3
A
B
7
D
5
8
A
B
D
9
B
C
6
D
C
D
1
6
9
5
3
7
D
D
8
4
3
9
7
5
2
B
B
A
8
C
A
8
C
C
D
C
B
7
B
B
A
2
D
B
4
9
4
7
8
D
C
5
4
B
8
1
D
B
5
C
A
2
C
B
8
1
4
3
4
D
6
3
B
B
B
1
6
D
A
4
A
6
D
D
B
B
B
C
7
B
D
B
B
2
5
4
D
5
B
A
2
D
A
1
C
10
3
8
A
D
A
6
B
7
7
5
2
2
6
9
3
5
4
1
5
B
5
A
A
6
C
9
6
2
2
C
A
7
5
A
6
6
A
9
C
D
B
7
B
3
D
9
6
2
B
B
D
1
5
5
7
1
9
D
D
6
2
D
3
B
A
1
B
4
B
A
A
A
7
C
A
D
B
5
3
D
C
D
D
5
4
5
9
7
5
C
4
D
4
A
B
8
2
D
C
A
A
A
9
A
C
D
7
B
A
4
D
B
D
9
D
3
1
4
A
6
5
10
2
1
9
A
C
A
D
D
3
B
4
8
A
2
2
5
8
D
C
B
7
4
B
1
C
5
5
C
D
2
B
8
5
9
A
9
5
2
A
2
C
A
B
D
2
6
D
C
A
1
A
4
4
B
4
D
6
6
4
2
2
5
5
5
D
5
C
8
A
C
9
B
3
D
8
C
A
B
D
B
1
C
B
8
C
5
4
B
A
C
C
9
C
A
D
C
B
8
D
A
3
A
5
C
8
B
8
D
4
9
3
C
B
5
8
1
4
4
3
D
B
7
3
A
9
A
4
D
C
7
C
1
C
9
6
4
A
D
2
3
A
A
1
D
10
3
4
7
D
C
8
D
C
8
4
A
D
6
C
C
5
1
B
C
2
5
7
3
6
6
7
7
6
A
9
B
8
D
9
7
7
2
B
B
1
5
C
2
9
C
5
3
5
3
4
A
C
9
A
B
Code: Select all
NO
NO
NO
NO
NO
NO
YES
1 C
3 D
5 C
6 D
7 D
NO
NO
NO
YES
2 B
7 C
YES
7 A
YES
1 C
YES
NO
YES
4 B
NO
NO
NO
NO
YES
6 D
NO
NO
NO
NO
NO
NO
NO
YES
7 D
YES
1 D
4 D
5 D
NO
NO
NO
NO
NO
YES
4 B
9 B
NO
YES
4 B
6 C
NO
YES
5 A
YES
2 D
NO
NO
NO
NO
YES
2 C
NO
NO
NO
NO
YES
2 B
4 A
9 D
YES
5 A
6 A
NO
NO
YES
8 A
NO
NO
NO
NO
NO
YES
1 B
3 D
NO
NO
NO
YES
3 B
4 D
6 B
7 B
NO
YES
NO
YES
1 A
4 A
5 A
8 A
NO
YES
1 D
3 C
5 D
6 D
7 D
YES
5 A
7 B
9 B
NO
NO
NO
NO
NO
NO
YES
2 A
6 A
9 A
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
2 D
4 D
5 D
6 D
NO
NO
NO
YES
1 B
8 C
NO
YES
1 D
6 C
NO
NO
YES
3 A
6 A
7 B
9 A
NO
NO
Code: Select all
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <memory.h>
#include <utility>
#include <stack>
#include <queue>
#include <vector>
#include <ctime>
#include <algorithm>
#include <map>
#define REP(i, a, b) \
for(int i = int(a); i <= int(b); i++)
using namespace std;
typedef long long ll;
//Modified Halim's
vector<int> pset(1000);
void initSet(int _size) {pset.resize(_size); REP(i, 0, _size - 1) pset[i] = i; }
int findSet(int i) { return pset[i] == i ? i : (pset[i] = findSet(pset[i])); } //Gets representative for node i, and performs path compression
void unionSet(int i, int j) { pset[findSet(i)] = findSet(j); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
int numberOfSets() { int n = 0; REP(i, 0, pset.size() - 1) n += (findSet(i) == i); return n; }
int sizeOfSet(int i) { int s = 0; REP(j, 0, pset.size() - 1) s += (findSet(i) == findSet(j)); return s; }
map<int, char> mut;
map<char, int> invMut;
int main(){
//FILE * fout = fopen("data.out", "w");
int n, cnum = 0, mN = 10;
char c, s[50];
while(gets(s) && strcmp(s, "") != 0){
if(cnum++) printf("\n\n");
sscanf(s, "%d", &n);
string s1 = "", s2 = "";
for(int i = 0; i < 2 * n; i++){
scanf("%c", &c);
if(i < n) s1 += c;
else s2 += c;
gets(s);
}
for(int i = 0; i < mN; i++){
mut[i] = '-';
invMut['A' + i] = -1;
}
initSet(mN);
bool flag = false, c1, c2;
for(int i = 0; i < n; i++){
//cout << endl << i << " " << s1[i] << " " << s2[i] << endl;
if(s1[i] == s2[i]) continue;
c1 = s1[i] >= 'A' && s1[i] <= 'Z';
c2 = s2[i] >= 'A' && s2[i] <= 'Z';
int v1 = -1, v2 = -1;
if(!c1) v1 = s1[i] - '1';
if(!c2) v2 = s2[i] - '1';
//cout << c1 << " " << c2 << endl << v1 << " " << v2 << endl;;
if(c1 && c2){
if(s1[i] != s2[i]){
flag = 1;
break;
}
}
if(!c1 && !c2){
if(findSet(v1) == findSet(v2)) continue;
else if(mut[findSet(v1)] == '-'){
unionSet(v1, v2);
}
else if(mut[findSet(v2)] == '-'){
unionSet(v2, v1);
}
else if(mut[findSet(v1)] != mut[findSet(v2)]){
flag = 1;
break;
}
}
else if(c1){
if(mut[findSet(v2)] != '-' && mut[findSet(v2)] != s1[i]){
flag = 1;
break;
}
else{
int mergeTo = invMut[s1[i]];
if(mergeTo != -1){
unionSet(v2, mergeTo);
invMut[s1[i]] = findSet(v2);
}
else{
mut[findSet(v2)] = s1[i];
invMut[s1[i]] = findSet(v2);
}
}
}
else {
if(mut[findSet(v1)] != '-' && mut[findSet(v1)] != s1[i]){
flag = 1;
break;
}
else{
int mergeTo = invMut[s2[i]];
if(mergeTo != -1){
unionSet(v1, mergeTo);
invMut[s2[i]] = findSet(v1);
}
else{
mut[findSet(v1)] = s2[i];
invMut[s2[i]] = findSet(v1);
}
}
}
/*for(int j = 0; j < 8; j++){
//if(mut[findSet(j)] != '-')
printf("%d %d %c\n", (j + 1), findSet(j) + 1, mut[findSet(j)]);
}*/
}
if(flag){
printf("NO");
}
else{
printf("YES");
for(int j = 0; j < mN; j++){
if(mut[findSet(j)] != '-'){
printf("\n");
printf("%d %c", (j + 1), mut[findSet(j)]);
}
}
}
if(!gets(s)) return 0;
}
}
Code: Select all
3
5
6
6
B
A
A
Code: Select all
YES
5 B
6 A