#ifdef NACHIA #define _GLIBCXX_DEBUG #else // disable assert #define NDEBUG #endif #include #include #include #include using namespace std; using ll = long long; const ll INF = 1ll << 60; #define REP(i,n) for(ll i=0; i using V = vector; template void chmax(A& l, const B& r){ if(l < r) l = r; } template void chmin(A& l, const B& r){ if(r < l) l = r; } pair, V> eulerian_trail( int N, const V>& edges, bool directed, int start = -1) { int M = edges.size(); if(!M) return { {0}, {} }; V X(M), D(N); V> G(N); REP(m,M){ auto [u,v] = edges[m]; G[u].push_back(m); if (!directed) G[v].push_back(m); X[m] = u + v; } if(start < 0) { start = edges[0].first; for(auto [u,v] : edges){ D[u] += 1; D[v] += directed ? -1 : 1; } REP(i, N) if(D[i] % 2 == 1) start = i; } V H(M+1,start), E(M), U(M, 0), K(N); REP(i,N) K[i] = G[i].size(); int p = 0, q = M; while (q) { int v = H[p]; while (0 < K[v]-- && U[G[v][K[v]]]) ; if (K[v] < 0) { if (!p) return {{-1}, {-1}}; H[q--] = H[p--]; E[q] = E[p]; } else { auto e = G[v][K[v]]; U[e] = 1; E[p++] = e; H[p] = X[e] - v; } } REP(i, M) if(X[E[i]] != H[i] + H[i + 1]) return { {-1}, {-1} }; return {H, E}; } void testcase(){ V> edges; REP(i,26) REP(j,26) edges.push_back({ i, j }); auto ei = eulerian_trail(26, edges, true).second; for(auto e : ei){ cout << char('A' + e / 26) << char('A' + e % 26) << "\n"; } } int main(){ cin.tie(0)->sync_with_stdio(0); // ll T; cin >> T; REP(t,T) testcase(); return 0; }