fn main() { input! { n: usize, m: usize, e: [(usize1, usize1); m], } let mut g = vec![0usize; n]; for &(a, b) in e.iter() { assert!(a.max(b) < n); assert!(a != b); assert!(g[a] >> b & 1 == 0); g[a] |= 1 << b; g[b] |= 1 << a; } let mut res = vec![0u64; 1 << n]; for (s, h) in g.iter().enumerate().rev() { let g = &g[..s]; let res = &mut res[(1 << s)..]; res[0] = 1; let mut dp = vec![vec![0; 1 << s]; s]; for i in 0..s { if *h >> i & 1 == 1 { dp[i][1 << i] = 1; } } for bit in 2usize..(1 << s) { let k = bit.trailing_zeros() as usize; for (src, g) in g.iter().enumerate() { if *g >> k & 1 == 0 { continue; } let dp_s = std::mem::take(&mut dp[src]); let v = &dp_s[(bit - (1 << k))..bit]; for (dp, v) in dp[k][bit..].iter_mut().zip(v.iter()) { *dp += *v; } dp[src] = dp_s; } if bit.count_ones() > 1 { for (dp, g) in dp.iter().zip(g.iter()) { if *g >> s & 1 == 1 { res[bit] += dp[bit]; } } } } } let mut dp = res; for (i, dp) in dp.iter_mut().enumerate() { if i.count_ones() > 1 { *dp /= 2; } } for &(a, b) in e.iter() { let mask = (1 << a) | (1 << b); let l = dp .iter() .enumerate() .filter(|p| p.0 & mask == 1 << a) .map(|p| *p.1) .collect::>(); let r = dp .iter() .enumerate() .filter(|p| p.0 & mask == 1 << b) .map(|p| *p.1) .collect::>(); let c = subset_convolution(&l, &r); let it = dp .iter_mut() .enumerate() .filter(|p| p.0 & mask == mask) .map(|p| p.1); for (dp, c) in it.zip(c) { *dp += c; } } let ans = subset_exp(&dp)[(1 << n) - 1]; println!("{}", ans); } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] 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_export] 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_export] 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 ---------- pub fn subset_convolution(a: &[T], b: &[T]) -> Vec where T: Ring + Copy, { let size = a.len().next_power_of_two(); assert!(size > 0 && a.len() == size && b.len() == size); let n = size.trailing_zeros() as usize; let mut x = vec![T::zero(); (n + 1) << n]; let mut y = vec![T::zero(); (n + 1) << n]; for (x, a) in [(&mut x, a), (&mut y, b)].iter_mut() { for (i, (x, a)) in x.chunks_exact_mut(n + 1).zip(a.iter()).enumerate() { x[i.count_ones() as usize] = *a; } } // #[target_feature(enable = "avx2")] unsafe fn rec(x: &mut [T], y: &mut [T], len: usize, cnt: usize) where T: Ring + Copy, { if x.len() == len { let mut buf = [T::zero(); 21]; let buf = &mut buf[..len]; let a = &x[..=cnt]; let b = &y[..=cnt]; for (i, x) in a.iter().enumerate() { let g = cnt - i; for (buf, y) in buf[(i + g)..].iter_mut().zip(b[g..].iter()) { *buf = *buf + *x * *y; } } x.copy_from_slice(buf); return; } let m = x.len() / 2; let (a, b) = x.split_at_mut(m); let (c, d) = y.split_at_mut(m); let ba = b.iter_mut().zip(a.iter()); let dc = d.iter_mut().zip(c.iter()); for ((b, a), (d, c)) in ba.zip(dc) { *b = *b + *a; *d = *d + *c; } rec(a, c, len, cnt); rec(b, d, len, cnt + 1); for (b, a) in b.iter_mut().zip(a.iter()) { *b = *b - *a; } } unsafe { rec(&mut x, &mut y, n + 1, 0); } x.chunks_exact(n + 1) .enumerate() .map(|(i, x)| x[i.count_ones() as usize]) .collect() } pub fn subset_exp(a: &[T]) -> Vec where T: Ring + Copy, { let size = a.len().next_power_of_two(); assert!(size > 0 && a.len() == size && a[0].is_zero()); let n = size.trailing_zeros() as usize; let mut res = Vec::with_capacity(size); res.push(T::one()); res[0] = T::one(); for i in 0..n { let t = subset_convolution(&res, &a[(1 << i)..(2 << i)]); res.extend(t); } res } pub trait Ring: Zero + One + Sub {} use std::ops::*; pub trait Zero: Sized + Add { fn zero() -> Self; fn is_zero(&self) -> bool; } pub trait One: Sized + Mul { fn one() -> Self; } impl Zero for u64 { fn zero() -> Self { 0 } fn is_zero(&self) -> bool { *self == 0 } } impl One for u64 { fn one() -> Self { 1 } } impl Ring for u64 {}