'''
把单词当成一条从第一个字符到最后一个字符的边,判断组成的有向图有没有欧拉路径
'''
import sys
from collections import Counter
class MergeSetExt:
def __init__(self, max_key_val = 0, trans_key_func=None):
if trans_key_func is not None and max_key_val > 0:
# 如果能够提供转换key的回调,并查集内部用线性表存储
self.trans_key_callback = trans_key_func
self.m = [-1 for _ in range(max_key_val+1)]
self.__root2cluster_size = [0 for _ in range(max_key_val+1)]
else:
# 如果不能提供转换key的回调,并查集内部用hash表存储
self.trans_key_callback = None
self.m = {}
self.__root2cluster_size = {}
self.__root_cnt = 0
def getRoot(self, node):
buf = []
root = self.trans_key_callback(node) if self.trans_key_callback else node
while self.m[root] != root:
buf.append(root)
root = self.m[root]
for key in buf:
self.m[key] = root
return root
def merge(self, a, b):
orig_a, orig_b = a, b
if self.trans_key_callback:
a, b = self.trans_key_callback(a), self.trans_key_callback(b)
for node in [a, b]:
if (self.trans_key_callback is None and node not in self.m) or (self.trans_key_callback is not None and self.m[node] == -1):
self.m[node] = node
self.__root2cluster_size[node] = 1
self.__root_cnt += 1
root1 = self.getRoot(orig_a)
root2 = self.getRoot(orig_b)
if root1 != root2:
self.m[root1] = root2
self.__root2cluster_size[root2] += self.__root2cluster_size[root1]
if self.trans_key_callback:
self.__root2cluster_size[root1] = 0
else:
self.__root2cluster_size.pop(root1)
self.__root_cnt -= 1
def getRootNum(self):
return self.__root_cnt
class HierholzerDirected:
def __init__(self, edges, node_num):
self.edges = edges[::]
self.node_num = node_num
def hasEulerPath(self) -> bool:
c = Counter()
merge_set = MergeSetExt(max_key_val=self.node_num, trans_key_func=lambda x: x)
for a, b in edges:
c[a] += 1
c[b] -= 1
merge_set.merge(a, b)
if merge_set.getRootNum() != 1:
# 图没有连成一块,不可能有欧拉路径或者欧拉回路
return None
p1, p2 = [], []
for key, val in c.items():
if val != 0:
if val == 1:
p1.append(key)
elif val == -1:
p2.append(key)
else:
return False
# 有起点和终点不同的欧拉路径或者有欧拉回路都满足要求
return (len(p1) == 1 and len(p2) == 1) or (len(p1) == 0 and len(p2) == 0)
t = int(input())
for _ in range(t):
n = int(input())
edges = []
nodes = set()
for i in range(n):
s = sys.stdin.readline().strip()
a, b = s[0], s[-1]
nodes.add(a)
nodes.add(b)
edges.append((a, b))
node2idx = {node:i+1 for i, node in enumerate(nodes)}
edges = [(node2idx[a], node2idx[b]) for a, b in edges]
algo = HierholzerDirected(edges, node_num = len(nodes))
print('The door cannot be opened.' if not algo.hasEulerPath() else 'Ordering is possible.')