fn main() { let stdin = std::io::read_to_string(std::io::stdin().lock()).unwrap(); let mut stdin = stdin.split_ascii_whitespace(); unsafe { read!(stdin -> (n: u32, q: u32, requests: Vec[(char, u32, u32); q])); write!(output(solve(n, requests))); } } fn solve(n: u32, requests: Vec<(char, u32, u32)>) -> u32 { let next_of = mylib::make_undirected_next_of_with_weight( (n + 1) as usize, requests.into_iter().map(|(tp, a, b)| (a, b, tp)), ); let mut count_group = n; let mut flag_at = vec![!0_u8; (n + 1) as usize]; let mut q = std::collections::VecDeque::new(); match (1..=n as usize).all(|start| { if flag_at[start] == !0 { flag_at[start] = 0; q.push_back(start as u32); while let Some(cur_pos) = q.pop_front() { for &(next, tp) in next_of[cur_pos as usize].iter() { if flag_at[next as usize] == !0 { flag_at[next as usize] = flag_at[cur_pos as usize] ^ (tp as u8 ^ b'0'); count_group -= 1; q.push_back(next); } else if flag_at[next as usize] != flag_at[cur_pos as usize] ^ (tp as u8 ^ b'0') { return false; } } } } true }) { true => mylib::pow_mod(2, count_group, 998244353), false => 0, } } fn output(ans: u32) -> String { format!("{}", ans) } mod mylib { pub fn make_undirected_next_of_with_weight( vertex_count: usize, edge_iter: impl Iterator, ) -> Vec> where usize: TryFrom, { let mut next_of = vec![Vec::new(); vertex_count]; edge_iter.for_each(|(u, v, w)| unsafe { next_of[usize::try_from(u).unwrap_unchecked()].push((v, w.clone())); next_of[usize::try_from(v).unwrap_unchecked()].push((u, w)); }); next_of } pub const fn pow_mod(a: u32, mut b: u32, r#mod: u32) -> u32 { let mut ans: u32 = 1; let mut mul: u32 = a; while b > 0 { if (b & 1) == 1 { ans = (ans as u64 * mul as u64 % r#mod as u64) as u32; } mul = (mul as u64 * mul as u64 % r#mod as u64) as u32; b /= 2; } ans } } #[macro_export] macro_rules! read { ($iter:ident -> ($v:ident : $t1:tt $([$($t2:tt)+] $({$($t3:tt)+})?)?)) => { let $v = read_value!($iter -> $t1 $([$($t2)+] $({$($t3)+})? )?); }; ($iter:ident -> ($v:ident : $t1:tt $([$($t2:tt)+] $({$($t3:tt)+})?)? , $($r:tt)*)) => { read!($iter -> ($v : $t1 $([$($t2)+] $({$($t3)+})?)?)); read!($iter -> ($($r)*)); }; } #[macro_export] macro_rules! read_line { ($iter:ident -> ($($r:tt)*)) => { let cur_line = $iter.next().unwrap().unwrap(); let mut cur_line = cur_line.split_ascii_whitespace(); read!(cur_line -> ($($r)*)) } } #[macro_export] macro_rules! read_value { ($source:ident -> ($($t1:tt $([$($t2:tt)+])?),+)) => { ( $(read_value!($source -> $t1 $([$($t2)+])?)),* ) }; ($source:ident -> [ $t1:tt $([$($t3:tt)+])? ; $len:expr ]) => { ::std::array::from_fn::<_, $len, _>(|_| read_value!($source -> $t1 $([$($t3)+])?)) }; ($source:ident -> $t1:tt[ $t2:tt $([$($t3:tt)+])? ; $len:expr ]) => { (0..($len)).map(|_| read_value!($source -> $t2 $([$($t3)+])?)).collect::<$t1<_>>() }; ($source:ident -> $t1:tt[ $t2:tt $([$($t3:tt)+])? ]) => { (0..(read_value!($source -> u32))).map(|_| read_value!($source -> $t2 $([$($t3)+])?)).collect::<$t1<_>>() }; ($source:ident -> $t1:tt[ ($($t2:tt),+) ; $len:expr ] { $($p1:pat => ($($pos:tt),*)),* }) => { (0..($len)).map(|_| { let mut v = ($($t2::default()),+); v.0 = my_parser::parse_without_checking(($source).next().unwrap()); match v.0 { $($p1 => { $(v.$pos = my_parser::parse_without_checking(($source).next().unwrap()));* }),* _ => unreachable!(), } v }).collect::<$t1<_>>() }; ($source:ident -> $t1:tt[ ($($t2:tt),+) ] { $($p1:pat => ($($pos:tt),*)),* }) => { read_value!($source -> $t1[ ($($t2),+) ; read_value!($source -> u32) ] { $($p1 => ($($pos),*)),* }) }; ($source:ident -> $t:ty) => { my_parser::parse_without_checking::<$t>(($source).next().unwrap()) }; } mod my_parser { #[allow(unused)] pub unsafe fn parse_without_checking(target: &str) -> F { unsafe { Parsable::from_str(target) } } pub trait Parsable { unsafe fn from_str(s: &str) -> Self; } impl Parsable for String { unsafe fn from_str(s: &str) -> Self { Self::from(s) } } impl Parsable for char { unsafe fn from_str(s: &str) -> Self { s.chars().next().unwrap() } } macro_rules! parse_float { ($s:ident) => {{ let mut iter = $s.bytes().peekable(); let sign = match iter.peek().unwrap() { b'-' => { iter.next(); -1.0 } b'+' => { iter.next(); 1.0 } _ => 1.0, }; let mut result = 0.0; while let Some(cur) = iter.next() { if cur == b'.' { break; } result = result * 10.0 + (cur - b'0') as Self; } let mut digit = 1.0; (result + iter .map(|cur| { digit *= 0.1; digit * (cur - b'0') as Self }) .sum::()) * sign }}; } impl Parsable for u8 { unsafe fn from_str(s: &str) -> Self { ((((s.bytes().fold(0, |acc, x| (acc << 8) | (x as u32)) & 0x0f0f0f0f) .wrapping_mul((1 << 8) + 10) >> 8) & 0x00ff00ff) .wrapping_mul((1 << 16) + 100) >> 16) as Self } } impl Parsable for u16 { unsafe fn from_str(s: &str) -> Self { ((((((s.bytes().fold(0, |acc, x| (acc << 8) | (x as u64)) & 0x0f0f0f0f0f0f0f0f) .wrapping_mul((1 << 8) + 10) >> 8) & 0x00ff00ff00ff00ff) .wrapping_mul((1 << 16) + 100) >> 16) & 0x0000ffff0000ffff) .wrapping_mul((1 << 32) + 10000) >> 32) as Self } } impl Parsable for u32 { unsafe fn from_str(s: &str) -> Self { ((((((((s.bytes().fold(0, |acc, x| (acc << 8) | (x as u128)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f) .wrapping_mul((1 << 8) + 10) >> 8) & 0x00ff00ff00ff00ff00ff00ff00ff00ff) .wrapping_mul((1 << 16) + 100) >> 16) & 0x0000ffff0000ffff0000ffff0000ffff) .wrapping_mul((1 << 32) + 10000) >> 32) & 0x00000000ffffffff00000000ffffffff) .wrapping_mul((1 << 64) + 100000000) >> 64) as Self } } impl Parsable for u64 { unsafe fn from_str(s: &str) -> Self { const POW_10: [u64; 17] = [ 1, 10, 100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000, 1_000_000_000, 10_000_000_000, 100_000_000_000, 1_000_000_000_000, 10_000_000_000_000, 100_000_000_000_000, 1_000_000_000_000_000, 10_000_000_000_000_000, ]; s.as_bytes().chunks(16).fold(0, |acc, x| { acc * POW_10[x.len()] + ((((((((x.iter().fold(0, |acc, &x| (acc << 8) | (x as u128)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f) .wrapping_mul((1 << 8) + 10) >> 8) & 0x00ff00ff00ff00ff00ff00ff00ff00ff) .wrapping_mul((1 << 16) + 100) >> 16) & 0x0000ffff0000ffff0000ffff0000ffff) .wrapping_mul((1 << 32) + 10000) >> 32) & 0x00000000ffffffff00000000ffffffff) .wrapping_mul((1 << 64) + 100000000) >> 64) as Self }) } } impl Parsable for u128 { unsafe fn from_str(s: &str) -> Self { const POW_10: [u128; 17] = [ 1, 10, 100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000, 1_000_000_000, 10_000_000_000, 100_000_000_000, 1_000_000_000_000, 10_000_000_000_000, 100_000_000_000_000, 1_000_000_000_000_000, 10_000_000_000_000_000, ]; s.as_bytes().chunks(16).fold(0, |acc, x| { acc * POW_10[x.len()] + ((((((((x.iter().fold(0, |acc, &x| (acc << 8) | (x as u128)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f) .wrapping_mul((1 << 8) + 10) >> 8) & 0x00ff00ff00ff00ff00ff00ff00ff00ff) .wrapping_mul((1 << 16) + 100) >> 16) & 0x0000ffff0000ffff0000ffff0000ffff) .wrapping_mul((1 << 32) + 10000) >> 32) & 0x00000000ffffffff00000000ffffffff) .wrapping_mul((1 << 64) + 100000000) >> 64) as Self }) } } impl Parsable for i8 { unsafe fn from_str(s: &str) -> Self { ((((((s .bytes() .skip(match s.as_bytes()[0].is_ascii_digit() { true => 0, false => 1, }) .fold(0, |acc, x| (acc << 8) | (x as u32)) & 0x0f0f0f0f) .wrapping_mul((1 << 8) + 10) >> 8) & 0x00ff00ff) .wrapping_mul((1 << 16) + 100) >> 16) as i32) * match s.as_bytes()[0] == b'-' { true => -1, false => 1, }) as Self } } impl Parsable for i16 { unsafe fn from_str(s: &str) -> Self { ((((((((s .bytes() .skip(match s.as_bytes()[0].is_ascii_digit() { true => 0, false => 1, }) .fold(0, |acc, x| (acc << 8) | (x as u64)) & 0x0f0f0f0f0f0f0f0f) .wrapping_mul((1 << 8) + 10) >> 8) & 0x00ff00ff00ff00ff) .wrapping_mul((1 << 16) + 100) >> 16) & 0x0000ffff0000ffff) .wrapping_mul((1 << 32) + 10000) >> 32) as i64) * match s.as_bytes()[0] == b'-' { true => -1, false => 1, }) as Self } } impl Parsable for i32 { unsafe fn from_str(s: &str) -> Self { ((((((((((s .bytes() .skip(match s.as_bytes()[0].is_ascii_digit() { true => 0, false => 1, }) .fold(0, |acc, x| (acc << 8) | (x as u128)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f) .wrapping_mul((1 << 8) + 10) >> 8) & 0x00ff00ff00ff00ff00ff00ff00ff00ff) .wrapping_mul((1 << 16) + 100) >> 16) & 0x0000ffff0000ffff0000ffff0000ffff) .wrapping_mul((1 << 32) + 10000) >> 32) & 0x00000000ffffffff00000000ffffffff) .wrapping_mul((1 << 64) + 100000000) >> 64) as i128) * match s.as_bytes()[0] == b'-' { true => -1, false => 1, }) as Self } } impl Parsable for i64 { unsafe fn from_str(s: &str) -> Self { const POW_10: [u64; 17] = [ 1, 10, 100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000, 1_000_000_000, 10_000_000_000, 100_000_000_000, 1_000_000_000_000, 10_000_000_000_000, 100_000_000_000_000, 1_000_000_000_000_000, 10_000_000_000_000_000, ]; let skip = match s.as_bytes()[0].is_ascii_digit() { true => 0, false => 1, }; ((s.as_bytes()[skip..].chunks(16).fold(0, |acc, x| { acc * POW_10[x.len()] + ((((((((x.iter().fold(0, |acc, &x| (acc << 8) | (x as u128)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f) .wrapping_mul((1 << 8) + 10) >> 8) & 0x00ff00ff00ff00ff00ff00ff00ff00ff) .wrapping_mul((1 << 16) + 100) >> 16) & 0x0000ffff0000ffff0000ffff0000ffff) .wrapping_mul((1 << 32) + 10000) >> 32) & 0x00000000ffffffff00000000ffffffff) .wrapping_mul((1 << 64) + 100000000) >> 64) as u64 }) as i64) * match s.as_bytes()[0] == b'-' { true => -1, false => 1, }) as Self } } impl Parsable for i128 { unsafe fn from_str(s: &str) -> Self { const POW_10: [u128; 17] = [ 1, 10, 100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000, 1_000_000_000, 10_000_000_000, 100_000_000_000, 1_000_000_000_000, 10_000_000_000_000, 100_000_000_000_000, 1_000_000_000_000_000, 10_000_000_000_000_000, ]; let skip = match s.as_bytes()[0].is_ascii_digit() { true => 0, false => 1, }; ((s.as_bytes()[skip..].chunks(16).fold(0, |acc, x| { acc * POW_10[x.len()] + ((((((((x.iter().fold(0, |acc, &x| (acc << 8) | (x as u128)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f) .wrapping_mul((1 << 8) + 10) >> 8) & 0x00ff00ff00ff00ff00ff00ff00ff00ff) .wrapping_mul((1 << 16) + 100) >> 16) & 0x0000ffff0000ffff0000ffff0000ffff) .wrapping_mul((1 << 32) + 10000) >> 32) & 0x00000000ffffffff00000000ffffffff) .wrapping_mul((1 << 64) + 100000000) >> 64) }) as i128) * match s.as_bytes()[0] == b'-' { true => -1, false => 1, }) as Self } } impl Parsable for f32 { unsafe fn from_str(s: &str) -> Self { parse_float!(s) } } impl Parsable for f64 { unsafe fn from_str(s: &str) -> Self { parse_float!(s) } } } #[macro_export] macro_rules! write { ($out:expr) => {{ use std::io::Write; std::io::stdout() .lock() .write_all(($out).as_bytes()) .unwrap(); }}; } #[macro_export] macro_rules! format_iter { ($i:expr, $sep:expr, ($($elem:ident),+) -> ($form:expr $(, $ex:expr)*)) => {{ #[allow(unused_parens)] let ($($elem),+) = i.next().unwrap(); #[allow(unused_parens)] $i.fold(std::format!($form $(, $ex)*), |mut acc, ($($elem),+)| { use std::fmt::Write; acc.push_str($sep); std::write!(&mut acc, $form $(, $ex)*).unwrap(); acc }) }} } #[macro_export] macro_rules! format_vec { ($v:expr, $sep:expr, ($($elem:ident),+) -> ($form:expr $(, $ex:expr)*)) => {{ if $v.is_empty() { String::new() } else { let mut iter = $v.into_iter(); #[allow(unused_parens)] let ($($elem),+) = iter.next().unwrap(); #[allow(unused_parens)] iter.fold(std::format!($form $(, $ex)*), |mut acc, ($($elem),+)| { use std::fmt::Write; acc.push_str($sep); std::write!(&mut acc, $form $(, $ex)*).unwrap(); acc }) } }} } #[macro_export] macro_rules! format_vec_vec { ($v:expr, $sep1:expr, $sep2:expr, ($($elem:ident),+) -> ($form:expr $(, $ex:expr)*)) => {{ let mut iter = $v.into_iter(); let v_first = iter.next().unwrap(); #[allow(unused_parens)] iter.fold(format_vec!(v_first, $sep2, ($($elem),+) -> ($form $(, $ex)*)), |mut acc, v| { use std::fmt::Write; acc.push_str($sep1); if !v.is_empty() { let mut iter_inner = v.into_iter(); #[allow(unused_parens)] let ($($elem),+) = iter_inner.next().unwrap(); std::write!(&mut acc, $form $(, $ex)*).unwrap(); iter_inner.fold(acc, |mut acc, ($($elem),+)| { acc.push_str($sep2); std::write!(&mut acc, $form $(, $ex)*).unwrap(); acc }) } }) }} }