#include #include #include #include #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(x) begin(x),end(x) #define sz(x) (int)(x).size() using namespace std; using namespace atcoder; using ll=long long; using ld=long double; using vll=vector; using vvll=vector; using vi=vector; using vvi=vector; using pll=pair; using pi=pair; // using mint=modint998244353; // using mint2=static_modint<2>; // using BoostPoint=boost::polygon::point_data; // using Voronoi=boost::polygon::voronoi_diagram; #line 2 "graph/others/eulerian-trail.hpp" #include #include #include #include #include #include #line 2 "structure/union-find/union-find.hpp" #line 4 "structure/union-find/union-find.hpp" #include #line 7 "structure/union-find/union-find.hpp" struct UnionFind { std::vector data; UnionFind() = default; explicit UnionFind(std::size_t sz) : data(sz, -1) {} bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return false; if (data[x] > data[y]) std::swap(x, y); data[x] += data[y]; data[y] = x; return true; } int find(int k) { if (data[k] < 0) return (k); return data[k] = find(data[k]); } int size(int k) { return -data[find(k)]; } bool same(int x, int y) { return find(x) == find(y); } std::vector> groups() { int n = (int)data.size(); std::vector> ret(n); for (int i = 0; i < n; i++) { ret[find(i)].emplace_back(i); } ret.erase( std::remove_if(ret.begin(), ret.end(), [&](const std::vector& v) { return v.empty(); }), ret.end()); return ret; } }; #line 11 "graph/others/eulerian-trail.hpp" /** * @brief Eulerian Trail(オイラー路) * */ template struct EulerianTrail { std::vector > > g; std::vector > es; int M; std::vector used_vertex, used_edge, deg; explicit EulerianTrail(int V) : g(V), M(0), used_vertex(V), deg(V) {} void add_edge(int a, int b) { es.emplace_back(a, b); g[a].emplace_back(b, M); if (directed) { deg[a]++; deg[b]--; } else { g[b].emplace_back(a, M); deg[a]++; deg[b]++; } M++; } std::pair get_edge(int idx) const { return es[idx]; } std::vector > enumerate_eulerian_trail() { if (directed) { for (auto& p : deg) if (p != 0) return {}; } else { for (auto& p : deg) if (p & 1) return {}; } used_edge.assign(M, 0); std::vector > ret; for (int i = 0; i < (int)g.size(); i++) { if (g[i].empty() || used_vertex[i]) continue; ret.emplace_back(go(i)); } return ret; } std::vector > enumerate_semi_eulerian_trail() { UnionFind uf(g.size()); for (auto& p : es) uf.unite(p.first, p.second); std::vector > group(g.size()); for (int i = 0; i < (int)g.size(); i++) group[uf.find(i)].emplace_back(i); std::vector > ret; used_edge.assign(M, 0); for (auto& vs : group) { if (vs.empty()) continue; int latte = -1, malta = -1; if (directed) { for (auto& p : vs) { if (std::abs(deg[p]) > 1) { return {}; } else if (deg[p] == 1) { if (latte >= 0) return {}; latte = p; } } } else { for (auto& p : vs) { if (deg[p] & 1) { if (latte == -1) latte = p; else if (malta == -1) malta = p; else return {}; } } } ret.emplace_back(go(latte == -1 ? vs.front() : latte)); if (ret.back().empty()) ret.pop_back(); } return ret; } std::vector go(int s) { std::stack > st; std::vector ord; st.emplace(s, -1); while (!st.empty()) { int idx = st.top().first; used_vertex[idx] = true; if (g[idx].empty()) { ord.emplace_back(st.top().second); st.pop(); } else { auto e = g[idx].back(); g[idx].pop_back(); if (used_edge[e.second]) continue; used_edge[e.second] = true; st.emplace(e); } } ord.pop_back(); std::reverse(ord.begin(), ord.end()); return ord; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin>>N; vi a(N),b(N),ans(N,-1),rev(N,-1),deg(N,0); vvi g(N); rep(i,0,N){ cin>>a[i]>>b[i]; a[i]--,b[i]--; if(a[i]==b[i]){ ans[i]=a[i]; rev[a[i]]=i; continue; } g[a[i]].push_back(i); g[b[i]].push_back(i); deg[a[i]]++,deg[b[i]]++; } queueq; rep(i,0,N){ if(deg[i]==1)q.push(i); } while(!q.empty()){ int ball=q.front(); q.pop(); if(deg[ball]==0||rev[ball]!=-1)continue; for(auto op:g[ball]){ if(ans[op]==-1){ ans[op]=ball; rev[ball]=op; int other=(ball==a[op])?b[op]:a[op]; if(deg[other]>0){ deg[other]--; if(deg[other]==1)q.push(other); } break; } } deg[ball]=0; } int remainL=0,remainR=0; bool deg0=false; rep(i,0,N){ if(ans[i]==-1)remainR++; if(rev[i]==-1){ remainL++; if(deg[i]==0)deg0=true; } } if(remainL!=remainR||deg0){ cout<<"No\n"; return 0; } EulerianTrailet(2*N); rep(op,0,N){ if(ans[op]!=-1)continue; et.add_edge(a[op],op+N); et.add_edge(b[op],op+N); } for(auto& tour:et.enumerate_eulerian_trail()){ for(int j=0;j