|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 30;
|
|
|
|
|
|
int m;
|
|
|
int din[N], dout[N], p[N];
|
|
|
bool st[N];
|
|
|
|
|
|
int find(int x) {
|
|
|
if (p[x] != x) p[x] = find(p[x]);
|
|
|
return p[x];
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
char str[1010];
|
|
|
|
|
|
int T;
|
|
|
scanf("%d", &T);
|
|
|
while (T--) {
|
|
|
scanf("%d", &m);
|
|
|
memset(din, 0, sizeof din);
|
|
|
memset(dout, 0, sizeof dout);
|
|
|
memset(st, 0, sizeof st);
|
|
|
for (int i = 0; i < 26; i++) p[i] = i;
|
|
|
|
|
|
for (int i = 0; i < m; i++) {
|
|
|
scanf("%s", str);
|
|
|
int len = strlen(str);
|
|
|
int a = str[0] - 'a', b = str[len - 1] - 'a';
|
|
|
st[a] = st[b] = 1;
|
|
|
dout[a]++, din[b]++;
|
|
|
p[find(a)] = find(b);
|
|
|
}
|
|
|
|
|
|
// 利用欧拉图判断的定理检查
|
|
|
int start = 0, s = 0, e = 0, flag = 1; // start:起点，s:起点个数,e:终点个数
|
|
|
for (int i = 0; i < 26; i++)
|
|
|
if (din[i] != dout[i]) { // 如果入度与出度不相等,那么必须是一个起点，一个终点
|
|
|
if (din[i] == dout[i] - 1) // 入度=出度-1 ->起点
|
|
|
start = i, s++; // 记录起点
|
|
|
else if (din[i] == dout[i] + 1) // 入度=出度+1 ->终点
|
|
|
e++;
|
|
|
else { // 没有欧拉通路,标识start=-1,表示检查失败
|
|
|
start = -1;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
if (start == -1 || s > 1 || e > 1) flag = 0;
|
|
|
|
|
|
// 判连通
|
|
|
for (int i = 0; i < 26; i++) {
|
|
|
if (!st[i]) continue; // 只处理出现的点
|
|
|
if (find(start) != find(i)) { // 找到不是一个家庭的成员
|
|
|
flag = 0;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
if (flag)
|
|
|
puts("Ordering is possible.");
|
|
|
else
|
|
|
puts("The door cannot be opened.");
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
} |
