#line 1 "b.cpp" #include using namespace std; using ll=long long; const ll ILL=2167167167167167167; const int INF=2100000000; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define all(p) p.begin(),p.end() template using pq_ = priority_queue, greater>; template int LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template int UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,T b){if(b bool chmax(T &a,T b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;} template void vec_out(vector &p,int ty=0){ if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'< T vec_min(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;} template T vec_max(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;} template T vec_sum(vector &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;} int pop_count(long long a){int res=0;while(a){res+=(int)(a&1),a>>=1;}return res;} template T square(T a){return a * a;} #line 6 "/Users/Shared/po167_library/graph/Eulerian_trail.hpp" namespace po167{ /* * グラフを与える。 * 辺は pair で、{行き先、辺の index} * オイラーウォークが存在するなら、 * 頂点番号の列と辺番号の列をどちらも返す * 入力 : vector>> グラフ, 辺の数, start * 出力 : 頂点の列と辺の番号の列の pair * * start 地点について * -1 にしておくと、その後の dir をみて自動的に求める * dir : true -> 出次 - 入次 が大きいやつ * dir : false -> 奇数頂点のやつ * なかったら 0 とかになる * * */ std::pair, std::vector> Eulerian_trail( std::vector>> g, int n_edge, int start = -1, bool dir = false ){ int N = (int)g.size(); // スタート地点不定 if (start == -1){ // 有向グラフのとき if (dir){ std::vector sc(N); for (int i = 0; i < N; i++){ for (auto [to, ind] : g[i]){ sc[i]++; sc[to]--; } } start = 0; for (int i = 0; i < N; i++){ if ((int)g[i].empty()) continue; if (sc[i] >= sc[start]) start = i; } } // 無向グラフのとき else{ for (int i = 0; i < N; i++){ if ((int)g[i].size() % 2 == 1){ start = i; break; } } if (start == -1){ start = 0; for (int i = 0; i < N; i++){ if ((int)g[i].size() != 0){ start = i; break; } } } } } assert(0 <= start && start < N); // -1 はそもそも使われていないもの std::vector use_edge(n_edge, -1); std::vector st_var = {start}, st_edge = {-1}; std::vector res_var, res_edge; std::vector edge_index(N); std::vector deg(N); deg[start] = 1; // 実際に何本の辺があるのかと、n_edge の制約を満たしているか確認 int real_edge = 0; for (int i = 0; i < N; i++){ for (auto [a, b] : g[i]){ assert(0 <= a && a < N); assert(0 <= b && b < n_edge); if (use_edge[b] == -1){ use_edge[b] = 0; real_edge++; } } } while (!st_var.empty()){ int var = st_var.back(); int ind = edge_index[var]; if (ind == (int)g[var].size()){ res_var.push_back(var); res_edge.push_back(st_edge.back()); st_var.pop_back(); st_edge.pop_back(); continue; } if (use_edge[g[var][ind].second] == 0){ st_var.push_back(g[var][ind].first); use_edge[g[var][ind].second] = 1; st_edge.push_back(g[var][ind].second); deg[var]--; deg[g[var][ind].first]++; } edge_index[var]++; } for (auto x : deg) if (x < 0) return {{}, {}}; if (real_edge + 1 != (int)res_var.size()) return {{}, {}}; std::reverse(res_var.begin(), res_var.end()); res_edge.pop_back(); std::reverse(res_edge.begin(), res_edge.end()); return {res_var, res_edge}; } } #line 26 "b.cpp" void solve(); // DEAR MYSTERIES / TOMOO int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; rep(i, 0, t) solve(); } void solve(){ const int N = 26; vector>> G(N); rep(i, 0, N) rep(j, 0, N) { G[i].push_back({j, i * N + j}); } auto f = [&](int a) -> char { return a + 'A'; }; auto ans = po167::Eulerian_trail(G, N * N, 0); for (auto e : ans.second) { cout << f(e / N) << f(e % N) << "\n"; } }