struct SCC { n: usize, graph: Vec>, rev_graph: Vec>, post_order: Vec, component: Vec, } impl SCC { fn new(n: usize) -> SCC { SCC { n, graph: vec![Vec::new(); n], rev_graph: vec![Vec::new(); n], component: vec![n; n], post_order: Vec::with_capacity(n), } } fn add_edge(&mut self, from: usize, to: usize) { self.graph[from].push(to); self.rev_graph[to].push(from); } fn dfs(&mut self, from: usize) { self.component[from] = self.n + 1; for to in self.graph[from].to_owned() { if self.component[to] == self.n { self.dfs(to); } } self.post_order.push(from); } fn rev_dfs(&mut self, from: usize, k: usize) { self.component[from] = k; for to in self.rev_graph[from].to_owned() { if self.component[to] > self.n { self.rev_dfs(to, k); } } } fn solve(&mut self) { for i in 0..self.n { if self.component[i] == self.n { self.dfs(i); } } let mut k: usize = 0; for i in (0..self.n).rev() { if self.component[self.post_order[i]] > self.n { self.rev_dfs(self.post_order[i], k); k += 1; } } } } struct TwoSAT { n: usize, scc: SCC, } impl TwoSAT { fn new(n: usize) -> TwoSAT { TwoSAT { n, scc: SCC::new(n * 2), } } fn add_closure(&mut self, x: usize, y: usize) { self.scc.add_edge((x + self.n) % (self.n * 2), y); self.scc.add_edge((y + self.n) % (self.n * 2), x); } fn solve(&mut self) -> Option> { self.scc.solve(); let mut res = vec![false; self.n]; for i in 0..self.n { if self.scc.component[i] == self.scc.component[i + self.n] { return None; } res[i] = self.scc.component[i] > self.scc.component[i + self.n]; } Some(res) } } use std::io::{BufRead, Write}; fn main() { let stdin = std::io::stdin(); let stdout = std::io::stdout(); let mut reader = std::io::BufReader::new(stdin.lock()); let mut writer = std::io::BufWriter::new(stdout.lock()); let n: usize = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); buf.trim_end().parse().unwrap() }; let s: Vec = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let iter = buf.split_whitespace(); iter.map(|x| x.parse::().unwrap() - 1).collect() }; let t: Vec = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let iter = buf.split_whitespace(); iter.map(|x| x.parse::().unwrap() - 1).collect() }; let u: Vec = { let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let iter = buf.split_whitespace(); iter.map(|x| x.parse().unwrap()).collect() }; let m = n * n; let mut two_sat = TwoSAT::new(m); for i in 0..n { for j in 0..n { match u[i] { 0 => two_sat.add_closure(s[i] * n + j, j * n + t[i]), 1 => two_sat.add_closure(s[i] * n + j + m, j * n + t[i]), 2 => two_sat.add_closure(s[i] * n + j, j * n + t[i] + m), _ => two_sat.add_closure(s[i] * n + j + m, j * n + t[i] + m), } } } let ans = two_sat.solve(); let ans = match ans { Some(res) => res, None => { writeln!(writer, "-1").unwrap(); return; } }; for (i, &value) in ans.iter().enumerate() { write!(writer, "{}", if value { 1 } else { 0 }).unwrap(); write!(writer, "{}", if i % n < n - 1 { ' ' } else { '\n' }).unwrap(); } }