#include #include #include using namespace std; template struct Graph { public: using value_type = T; struct Edge { int from, to; T cost; int id; operator int() const { return to; } }; Graph() {} Graph(int n) : n(n), m(0), g(n) {} void add_directed_edge(int from, int to, T cost = 1) { assert(0 <= from && from < n); assert(0 <= to && to < n); g[from].push_back((Edge){from, to, cost, m++}); } void add_undirected_edge(int from, int to, T cost = 1) { assert(0 <= from && from < n); assert(0 <= to && to < n); g[from].push_back((Edge){from, to, cost, m}); g[to].push_back((Edge){to, from, cost, m++}); } int size() { return n; } int edge_size() { return m; } inline const std::vector &operator[](const int &u) const { return g[u]; } inline std::vector &operator[](const int &u) { return g[u]; } private: int n, m; std::vector> g; }; template struct LowLink { public: using EDGE = typename GRAPH::Edge; std::vector articulation; std::vector bridge; LowLink() {} LowLink(GRAPH &g) : n(g.size()), g(g) { std::vector ord(n, -1); std::vector low(n, -1); int k = 0; auto dfs = [&](auto self, int u, int last_edge_id) -> void { low[u] = ord[u] = k++; int c = 0; bool is_artification = false; for (auto e : g[u]) { int v = e.to; if (e.id == last_edge_id) { continue; } if (ord[v] == -1) { c++; self(self, v, e.id); if (last_edge_id != -1 && ord[u] <= low[v]) { is_artification = true; } if (ord[u] < low[v]) { bridge.push_back(e); } low[u] = std::min(low[u], low[v]); } low[u] = std::min(low[u], ord[v]); } is_artification |= (last_edge_id == -1 && c >= 2); if (is_artification) { articulation.push_back(u); } }; for (int u = 0; u < n; u++) { if (ord[u] == -1) { dfs(dfs, u, -1); } } } private: int n; const GRAPH &g; }; int main() { int n; cin >> n; Graph g(n); int a[200005], b[200005]; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i]; a[i]--; b[i]--; g.add_undirected_edge(a[i], b[i]); } int r = -1; int eid = -1; LowLink> low(g); { bool isbridge[200005]{0}; for (auto e : low.bridge) { isbridge[e.id] = true; } for (int i = 0; i < n; i++) { if (!isbridge[i]) { r = a[i]; eid = i; } } } bool used[200005]{0}; queue que; used[r] = true; que.push(r); bool ans[200005]; ans[eid] = true; while (que.size()) { int u = que.front(); que.pop(); for (auto e : g[u]) { int v = e.to; if (used[v] || e.id == eid) { continue; } if (a[e.id] == u) { ans[e.id] = false; } else { ans[e.id] = true; } used[v] = true; que.push(v); } } for (int i = 0; i < n; i++) { if (ans[i]) { cout << "->" << endl; } else { cout << "<-" << endl; } } }