// ---------- begin SCC ---------- pub struct SCC { size: usize, edge: Vec<(u32, u32)>, } impl SCC { pub fn new(size: usize) -> Self { assert!(size <= 10usize.pow(8)); SCC { size, edge: vec![] } } pub fn add_edge(&mut self, a: usize, b: usize) { assert!(a < self.size && b < self.size); self.edge.push((a as u32, b as u32)); } pub fn build(&self) -> (usize, Vec) { let size = self.size; let mut start = vec![0u32; size + 1]; self.edge.iter().for_each(|e| start[e.0 as usize + 1] += 1); for i in 1..=size { start[i] += start[i - 1]; } let mut buf = vec![0; self.edge.len()]; for &(a, b) in self.edge.iter() { let po = &mut start[a as usize]; buf[*po as usize] = b; *po += 1; } let mut s = 0usize; let mut neighbor = start .into_iter() .take(size) .map(|t| { let t = t as usize; let it = buf[s..t].iter().map(|p| *p as usize); s = t; it }) .collect::>(); let mut ord = vec![size; size]; let mut assigned = vec![false; size]; let mut stack_s = vec![]; let mut stack_p = vec![]; let mut call = vec![]; let mut now_ord = 0; let mut res = vec![0; size]; let mut id = 0; enum Operation { Call(usize), Iter(usize), Eval(usize), } for i in 0..size { if ord[i] != size { continue; } call.push(Operation::Call(i)); while let Some(op) = call.pop() { match op { Operation::Call(v) => { ord[v] = now_ord; now_ord += 1; stack_s.push(v); stack_p.push(v); call.push(Operation::Eval(v)); call.push(Operation::Iter(v)); } Operation::Iter(v) => { let it = &mut neighbor[v]; while let Some(u) = it.next() { if ord[u] == size { call.push(Operation::Iter(v)); call.push(Operation::Call(u)); break; } else if !assigned[u] { while ord[*stack_p.last().unwrap()] > ord[u] { stack_p.pop(); } } } } Operation::Eval(v) => { if *stack_p.last().unwrap() == v { while let Some(u) = stack_s.pop() { res[u] = id; assigned[u] = true; if u == v { break; } } stack_p.pop(); id += 1; } } } } } res.iter_mut().for_each(|v| *v = id - 1 - *v); (id, res) } } // ---------- end SCC ---------- // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- fn dfs( v: usize, g: &[Vec<(usize, usize)>], depth: &mut [usize], used: &mut [bool], state: &mut [usize], parent: &mut [(usize, usize)], ) { used[v] = true; let d = depth[v] + 1; for &(u, k) in g[v].iter() { if used[u] && depth[u] < depth[v] { state[k] = 2; } else { parent[u] = (v, k); depth[u] = d; state[k] = d & 1; dfs(u, g, depth, used, state, parent); } } } fn run() { input! { n: usize, m: usize, e: [(usize1, usize1); m], } let mut scc = SCC::new(n); let mut g = vec![vec![]; n]; for (i, &(a, b)) in e.iter().enumerate() { scc.add_edge(a, b); g[a].push((b, i)); } if scc.build().0 > 1 { println!("-1"); return; } for root in 0..n { let mut depth = vec![0; n]; let mut used = vec![false; n]; let mut state = vec![2; m]; let mut parent = vec![(n, m); n]; dfs(root, &g, &mut depth, &mut used, &mut state, &mut parent); let mut back = vec![]; for (i, state) in state.iter().enumerate() { if *state == 2 { let (s, t) = e[i]; back.push((s, t, i)); } } let cnt = state.iter().filter(|p| **p == 2).count() > 1; let elem = back .iter() .any(|&(s, t, _)| (depth[s] - depth[t] + 1) % 2 == 1); if !(cnt && elem) { continue; } let mut elem = [false; 2]; for &(s, t, k) in back.iter() { if (depth[s] - depth[t] + 1) % 2 == 1 { continue; } if depth[t] % 2 == 0 { state[k] = 1; elem[1] = true; } else { state[k] = 0; elem[0] = true; } } for &(s, t, k) in back.iter() { if (depth[s] - depth[t] + 1) % 2 == 0 { continue; } let x = elem.iter().position(|p| !*p).unwrap_or(0); state[k] = x; elem[x] = true; } let mut ans = String::new(); for state in state { if state == 0 { ans.push('R'); } else { ans.push('G'); } } println!("{}", ans); return; } println!("-1"); } fn main() { run(); }