pub mod scanner { pub struct Scanner { buf: Vec, } impl Scanner { pub fn new() -> Self { Self { buf: vec![] } } pub fn new_from(source: &str) -> Self { let source = String::from(source); let buf = Self::split(source); Self { buf } } pub fn next(&mut self) -> T { loop { if let Some(x) = self.buf.pop() { return x.parse().ok().expect(""); } let mut source = String::new(); std::io::stdin().read_line(&mut source).expect(""); self.buf = Self::split(source); } } fn split(source: String) -> Vec { source .split_whitespace() .rev() .map(String::from) .collect::>() } } } pub mod directed_graph { type Weight = isize; #[derive(Clone)] pub struct Edge { pub from: usize, pub to: usize, pub index: usize, pub weight: Weight, } pub struct DirectedGraph { pub n: usize, pub m: usize, pub edges: Vec>, pub orig_edges: Vec, pub degree: Vec, } impl DirectedGraph { pub fn new(n: usize, m: usize) -> Self { let edges = vec![vec![]; n]; let orig_edges = vec![]; let degree = vec![0; n]; Self { n, m, edges, orig_edges, degree, } } pub fn init(scanner: &mut crate::scanner::Scanner, indexed: usize) -> Self { let n: usize = scanner.next(); let m: usize = n; let mut graph = Self::new(n, m); for index in 0..m { let from: usize = scanner.next::() - indexed; let to: usize = scanner.next::() - indexed; let weight: Weight = 1; graph.orig_edges.push(Edge { from, to, index, weight, }); graph.add_edge(from, to, index, weight); graph.add_edge(to, from, index, weight); graph.degree[from] += 1; graph.degree[to] += 1; } graph } pub fn add_edge(&mut self, from: usize, to: usize, index: usize, weight: Weight) { let edge = Edge { from, to, index, weight, }; self.edges[from].push(edge); } } } use crate::{directed_graph::DirectedGraph, scanner::Scanner}; fn main() { let mut scanner = Scanner::new(); let t: usize = 1; for _ in 0..t { solve(&mut scanner); } } fn solve(scanner: &mut Scanner) { let mut graph = DirectedGraph::init(scanner, 1); let n = graph.n; let mut dir = vec![!0; n]; let mut que = std::collections::VecDeque::new(); for u in 0..n { if graph.degree[u] == 1 { que.push_back(u); } } while let Some(u) = que.pop_front() { for edge in graph.edges[u].iter_mut() { if dir[edge.index] == !0 { dir[edge.index] = u; graph.degree[edge.from] -= 1; graph.degree[edge.to] -= 1; if graph.degree[edge.to] == 1 { que.push_back(edge.to); } } } } let mut cur = 0; for u in 0..n { if graph.degree[u] == 2 { cur = u; break; } } loop { let mut updated = false; for edge in graph.edges[cur].iter_mut() { if graph.degree[edge.to] == 2 { dir[edge.index] = cur; graph.degree[edge.from] -= 1; graph.degree[edge.to] -= 1; cur = edge.to; updated = true; break; } } if !updated { break; } } for edge in graph.edges[cur].iter_mut() { if dir[edge.index] == !0 { dir[edge.index] = cur; break; } } for i in 0..n { if dir[i] == graph.orig_edges[i].from { println!("->"); } else { println!("<-"); } } }