#line 1 "main.cpp" #ifdef LOCAL #include #else #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2") #include #define debug(...) ((void)0) #define postprocess(...) ((void)0) #endif #line 1 "library/graph/shortest_path.hpp" #include template struct shortest_path { const weight unreachable = std::numeric_limits::max(); shortest_path() : _computed(false) {} shortest_path(const int& n, const int& m = 0) : _n(n), _computed(false) { if (m) _edges.reserve(m); } void set_number(const int& n, const int& m = 0) { _n = n; if (m) _edges.reserve(m); } void add_edge(const int& i, const int& j, const weight& w) { assert(0 <= i && i < _n); assert(0 <= j && j < _n); _edges.emplace_back(i, j, w); } void compute(const int& s) { _s = s; _computed = true; _adj.resize(_n); for (auto&& e : _edges) { auto [u, v, w] = e; _adj[u].emplace_back(v, w); } _dist.resize(_n); std::fill(_dist.begin(), _dist.end(), unreachable); _par.resize(_n); std::fill(_par.begin(), _par.end(), -1); // select best algorithm if (!std::is_integral::value) { _dijkstra(s); return; } for (auto&& [_, __, cost] : _edges) { if (cost >= 2) { _dijkstra(s); return; } } for (auto&& [_, __, cost] : _edges) { if (cost == 0) { _bfs01(s); return; } } _bfs(s); } int s() { assert(_computed); return _s; } std::vector dist() { assert(_computed); return _dist; } weight dist(const int& t) { assert(_computed); return _dist[t]; } std::vector path(int t) { assert(_computed); assert(0 <= t && t < _n); assert(_dist[t] != unreachable); std::vector ret; while (t != _s) { ret.push_back(t); t = _par[t]; } ret.push_back(_s); std::reverse(ret.begin(), ret.end()); return ret; } private: // input values int _n; int _s; std::vector> _edges; // computed values bool _computed; std::vector>> _adj; std::vector _dist; std::vector _par; void _bfs(const int& s) { std::queue que; que.emplace(s); _dist[s] = 0; while (!que.empty()) { auto v = que.front(); que.pop(); for (auto&& [to, _] : _adj[v]) { if (_dist[to] == unreachable) { _dist[to] = _dist[v] + 1; _par[to] = v; que.emplace(to); } } } } void _bfs01(const int& s) { std::deque que; _dist[s] = 0; que.emplace_back(s); while (!que.empty()) { auto v = que.front(); que.pop_front(); for (auto&& [to, cost] : _adj[v]) { weight d = _dist[v] + cost; if (d < _dist[to]) { _dist[to] = d; _par[to] = v; if (cost) { que.emplace_back(to); } else { que.emplace_front(to); } } } } } void _dijkstra(const int& s) { using que_class = std::pair; std::priority_queue, std::greater> que; _dist[s] = 0; que.emplace(0, s); while (!que.empty()) { auto [d, v] = que.top(); que.pop(); if (_dist[v] != d) continue; for (auto&& [to, cost] : _adj[v]) { if (_dist[to] <= d + cost) continue; _dist[to] = d + cost; _par[to] = v; que.emplace(_dist[to], to); } } } }; #line 12 "main.cpp" using namespace std; using ll = long long; using ld = long double; vector> adj; deque cycle; vector visited; bool rec(int par = -1, int v = 0) { if (visited[v]) { while (cycle.front() != v) cycle.pop_front(); return true; } visited[v] = true; cycle.push_back(v); for (auto&& u : adj[v]) { if (u == par) continue; if (rec(v, u)) return true; } cycle.pop_back(); return false; } void solve([[maybe_unused]] int test) { int N; cin >> N; adj.resize(N); visited = vector(N, false); map, int> edge; shortest_path sp(N); for (int i = 0; i < N; i++) { int A, B; cin >> A >> B; A--; B--; edge[{A, B}] = i; adj[A].push_back(B); adj[B].push_back(A); sp.add_edge(A, B, 1); sp.add_edge(B, A, 1); } rec(); bool in_cycle[N]; for (int i = 0; i < N; i++) { in_cycle[i] = false; } for (auto&& v : cycle) { in_cycle[v] = true; } bool ans[N]; for (int i = 0; i < (int)cycle.size(); i++) { bool right = true; int a = cycle[i]; int b = cycle[(i + 1) % (int)cycle.size()]; if (!(a < b)) swap(a, b), right = false; assert(edge.count({a, b})); int e = edge[{a, b}]; ans[e] = right; } sp.compute(cycle[0]); for (auto&& [E, e] : edge) { auto [a, b] = E; if (in_cycle[a] && in_cycle[b]) continue; ans[e] = sp.dist(a) > sp.dist(b); } for (int i = 0; i < N; i++) { cout << (ans[i] ? "->" : "<-") << endl; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { solve(i); } postprocess(); }