fn main() { let input = Input::read(); let mut map = ReduceMap::new(input.n); // map.print(); for (_, b, y) in &input.t { let mut visited = 0; for i in b { visited |= 1 << i; } // println!("{:0n$b}", visited, n = input.n); if !map.insert(visited, *y) { println!("-1"); return; } // map.print(); } // map.print(); let ans = map.construct(); for &i in &ans { println!("{}", i); } } #[derive(Debug)] struct Input { n: usize, m: usize, t: Vec<(usize, Vec, u32)>, } struct ReduceMap { vec: Vec<(u64, u32)>, } impl Input { fn read() -> Input { let stdin = std::io::stdin(); let (n, m) = { let mut s = String::new(); stdin.read_line(&mut s).unwrap(); let (prev, n) = { let index = s.find(' ').unwrap(); let n = s[..index].parse().unwrap(); (index + 1, n) }; let m = if let Some((index, '\n')) = s.char_indices().last() { s[prev..index].parse().unwrap() } else { panic!(); }; (n, m) }; let t = { let mut vec = Vec::new(); for _ in 0..m { let a = { let mut s = String::new(); stdin.read_line(&mut s).unwrap(); if let Some((index, '\n')) = s.char_indices().last() { s[..index].parse().unwrap() } else { panic!(); } }; let b = { let mut s = String::new(); stdin.read_line(&mut s).unwrap(); let mut v = Vec::new(); let mut prev = 0; for _ in 0..a - 1 { let index = prev + s[prev..].find(' ').unwrap(); v.push(s[prev..index].parse::().unwrap() - 1); prev = index + 1; } let tmp = if let Some((index, '\n')) = s.char_indices().last() { s[prev..index].parse::().unwrap() } else { panic!(); }; v.push(tmp - 1); v }; let y = { let mut s = String::new(); stdin.read_line(&mut s).unwrap(); if let Some((index, '\n')) = s.char_indices().last() { s[..index].parse().unwrap() } else { panic!(); } }; vec.push((a, b, y)); } vec }; assert_eq!(stdin.read_line(&mut String::new()).unwrap(), 0); Input { n: n, m: m, t: t } } } impl ReduceMap { fn new(n: usize) -> ReduceMap { ReduceMap { vec: vec![(0, 0); n], } } fn insert(&mut self, key: u64, value: u32) -> bool { if key == 0 { value == 0 } else { use std::convert::TryInto; let index: usize = key.trailing_zeros().try_into().unwrap(); let (ref mut k, ref mut v) = self.vec[index]; if *k == 0 { assert_eq!(*v, 0); *k = key; *v = value; true } else { let key = key ^ *k; let value = value ^ *v; self.insert(key, value) } } } fn construct(&self) -> Vec { let n = self.vec.len(); let mut ret = vec![0; n]; for (i, &(k, v)) in self.vec.iter().enumerate().rev() { if k != 0 { let mut x = v; for j in i + 1..n { if k >> j & 1 == 1 { x ^= ret[j]; } } ret[i] = x; } } ret } #[allow(unused)] fn print(&self) { for (k, v) in &self.vec { println!("{:0n$b}: {:b}", k, v, n = self.vec.len()); } } }