#include"bits/stdc++.h" using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } // graph template // ref : https://ei1333.github.io/library/graph/graph-template.cpp template struct Edge{ int from,to; T w; int idx; Edge()=default; Edge(int from,int to,T w=1,int idx=-1):from(from),to(to),w(w),idx(idx){} operator int() const{return to;} }; template struct Graph{ vector>> g; int V,E; Graph()=default; Graph(int n):g(n),V(n),E(0){} int size(){ return (int)g.size(); } void resize(int k){ g.resize(k); V=k; } inline const vector> &operator[](int k)const{ return (g.at(k)); } inline vector> &operator[](int k){ return (g.at(k)); } void add_directed_edge(int from,int to,T cost=1){ g[from].emplace_back(from,to,cost,E++); } void add_edge(int from,int to,T cost=1){ g[from].emplace_back(from,to,cost,E); g[to].emplace_back(to,from,cost,E++); } void read(int m,int pad=-1,bool weighted=false,bool directed=false){ for(int i=0;i>u>>v; u+=pad,v+=pad; T w=T(1); if(weighted) cin>>w; if(directed) add_directed_edge(u,v,w); else add_edge(u,v,w); } } }; /* Namori Graph loop_vertex[i] - loop_edge[i] loop_vertex[i+1] forest : loop_vertexからぶら下がる木 loop_vertexをroot, 0としてidふり直し */ template struct Namori{ Graph G; vector loop_vertex; vector> loop_edge; vector> forest; Namori(Graph G):G(G){ int N=G.size(); // loop 取り出し vector used(N, false); { vector deg(N); queue que; for(int i=0;i que; vector visited(N, false); for(int i=0;i id(N, -1); for(int root:loop_vertex){ vector> es; int V=0; function dfs=[&](int par, int cur){ for(auto &e:G[cur])if(par!=e and (used[e])){ if(id[e]==-1) id[e]=V++; es.emplace_back(id[cur], id[e], e.w, e.idx); dfs(cur, e); } }; id[root]=V++; dfs(-1, root); Graph g(V); for(auto &e:es) g.add_edge(e.from, e.to, e.w); forest.push_back(g); } } } }; signed main(){ int N;cin>>N; Graph G(N); rep(i, N){ int u,v;cin>>u>>v;u--,v--; G.add_edge(u, v); } Namori namori(G); // debug(namori.loop_vertex); cout<