#include using namespace std; using ll = long long; using pll = pair; #define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i) #define rep(i, n) drep(i, 0, n - 1) #define all(a) (a).begin(), (a).end() #define pb push_back #define fi first #define se second mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); const ll MOD1000000007 = 1000000007; const ll MOD998244353 = 998244353; const ll MOD[3] = {999727999, 1070777777, 1000000007}; const ll LINF = 1LL << 60; const int IINF = 1 << 30; template struct Edge{ int to; T w; Edge(int to_, T w_=1){ to = to_; w=w_; } }; template using Tree = vector>>; template using Graph = vector>>; /* 容量&重み付きエッジ for Dinic */ template struct REdge{ int to; T cap; T cost; int rev; REdge(int to_, T cap_, T cost_=1){ to = to_; cap = cap_; cost = cost_; } REdge(int to_, T cap_, T cost_, int rev_){ to = to_; cap = cap_; cost = cost_; rev = rev_; } }; /* 残余グラフ for Dinic */ template using RGraph = vector>>; template struct Namori{ int n; vector root; //root[閉路上の頂点]=自身の頂点, root[閉路外の頂点]=根頂点 vector par; //par[閉路上の頂点]=-1, par[閉路外の頂点]=親頂点 Namori(Graph &graph){ n = (int)graph.size(); root.resize(n, 0); for(int v=0; v &graph){ //閉路上の頂点を決定 vector deg(n, 0); for(int v=0; v Q; for(int v=0; v e : graph[v]){ deg[e.to]--; if(deg[e.to]==1) Q.push(e.to); } } function dfs = [&](int v, int p){ root[v] = root[p]; par[v] = p; for(Edge e : graph[v]) if(e.to != p) dfs(e.to, v); }; for(ll r=0; r e : graph[r]){ if(root[e.to]==e.to) continue; dfs(e.to, r); } } } int get_root(int v){return root[v];} int get_par(int v){return par[v];} }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; Graph G(n); vector> E(n); rep(i, n){ int a, b; cin >> a >> b; a--; b--; G[a].pb(Edge(b)); G[b].pb(Edge(a)); E[i] = {a, b}; } Namori nmr(G); vector ans(n, -1); for(int i=0; i>> Cycle(n); int s = 0; for(int i=0; i dfs = [&](int u, int p){ if(u == s) return; for(pair tmp : Cycle[u]){ int v = tmp.fi; int idx = tmp.se; if(p == v) continue; if(E[idx].fi==u) ans[idx] = 0; else ans[idx] = 1; dfs(v, u); } }; dfs(t, s); for(int i=0; i" << endl; else cout << "<-" << endl; } }