#include #include using namespace std; using namespace atcoder; typedef long long int ll; typedef long double ld; typedef vector vi; typedef vector vvi; typedef vector vvvi; typedef vector vvvvi; typedef pair pi; typedef pair ppi; typedef pair pppi; typedef pair ppppi; #define FOR(i,l,r) for(ll i=l;i=l;i--) #define RREP(i,n) RFOR(i,0,n) #define ALL(x) x.begin(),x.end() #define F first #define S second #define BS(A,x) binary_search(ALL(A),x) #define LB(A,x) (ll)(lower_bound(ALL(A),x)-A.begin()) #define UB(A,x) (ll)(upper_bound(ALL(A),x)-A.begin()) #define COU(A,x) (UB(A,x)-LB(A,x)) #define sz(c) ((ll)(c).size()) /* #include namespace mp=boost::multiprecision; using Bint=mp::cpp_int; */ templateusing min_priority_queue=priority_queue,greater>; templateostream&operator<<(ostream&os,pair&p){os<istream&operator>>(istream&is,pair&p){is>>p.F>>p.S;return is;} templateostream&operator<<(ostream&os,vector&v){REP(i,sz(v))os<istream&operator>>(istream&is,vector&v){for(T&in:v)is>>in;return is;} templatebool chmax(T&a,T b){if(abool chmin(T&a,T b){if(b vm; typedef vector vvm; typedef vector vvvm; typedef vector vvvvm; ostream&operator<<(ostream&os,mint&a){os<>N; vectores(N); cin>>es; vvi E(N); REP(i,N){ es[i].F--;es[i].S--; E[es[i].F].emplace_back(es[i].S); E[es[i].S].emplace_back(es[i].F); } vi P(N,-1); P[0]=0; queueQ; Q.emplace(0); while(sz(Q)){ ll v=Q.front();Q.pop(); for(auto u:E[v])if(P[u]==-1){P[u]=v;Q.emplace(u);} } setS,ans; FOR(i,1,N){ S.insert(pi(i,P[i])); S.insert(pi(P[i],i)); } ll t=0; while(S.count(es[t]))t++; ll r=es[t].F; REP(i,N)P[i]=-1; P[r]=r; Q.emplace(r); while(sz(Q)){ ll v=Q.front();Q.pop(); for(auto u:E[v])if(P[u]==-1){P[u]=v;Q.emplace(u);} } t=0; while(S.count(es[t]))t++; ll u=es[t].F,v=es[t].S; ans.insert(pi(u,v)); while(u!=r){ ans.insert(pi(P[u],u));u=P[u]; } while(v!=r){ ans.insert(pi(v,P[v]));v=P[v]; } REP(i,N)if(!ans.count(pi(i,P[i])))ans.insert(pi(i,P[i])); REP(i,N){ if(ans.count(es[i]))cout<<"->"<