#include <iostream> #include <cstring> using namespace std; const int N=30; // 26个字母的顶点 int din[N], dout[N]; // 顶点的出度和入度 int g[N][N]; int T, n, cnt; void dfs(int u){ for(int i=0; i<26; ++i){ if(g[u][i]){ ++cnt; --g[u][i]; dfs(i); } } } int main(){ string word; cin>>T; while(T--){ cnt=0; cin>>n; memset(din, 0x00, sizeof din); memset(dout, 0x00, sizeof dout); memset(g, 0x00, sizeof g); for(int i=0; i<n; ++i){ cin>>word; int x=word[0]-'a'; int y=word.back()-'a'; // 建立一条由x指向y的有向边 dout[x]++; din[y]++; g[x][y]++; } // 判断度数 int s=0, e=0; bool ok=true; for(int i=0; i<26; ++i) if(din[i]!=dout[i]){ if(din[i]==dout[i]+1) ++e; else if(din[i]+1==dout[i]) ++s; else {ok=false; break;} } // 有向图Euler path判定 // 或者起点和终点数量都是0(形成环) // 或者起点和终点数量都是1 if(!(!s&&!e||s==1 && e==1)) ok=false; // 判断连通性 int start=0; while(!dout[start]) ++start; for(int i=start; i<26; ++i){ if(dout[i]==din[i]+1) {start=i; break;} } dfs(start); if(cnt!=n) ok=false; if(ok) cout<<"Ordering is possible."<<endl; else cout<<"The door cannot be opened."<<endl; } return 0; }