fn run() { input! { n: usize, p: [(usize, usize); n], } let m = 1000000; let mut is_prime = vec![false; m + 1]; enumerate_prime(m, |p| is_prime[p] = true); let mut sat = SAT2::new(n); for (i, &(a, b)) in p.iter().enumerate() { for (j, &(c, d)) in p.iter().enumerate() { for &(a, x) in [(a, i), (b, !i)].iter() { for &(c, y) in [(c, j), (d, !j)].iter() { let v = format!("{}{}", a, c).parse::().unwrap(); if is_prime[v] { sat.either(!x, !y); } } } } } let ans = sat.solve(); if ans.is_some() { println!("Yes"); } else { println!("No"); } } fn main() { run(); } // ---------- 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 ---------- // ---------- begin 2-SAT ---------- pub struct SAT2 { size: usize, clause: Vec<(usize, usize)>, } impl SAT2 { pub fn new(size: usize) -> Self { SAT2 { size: size, clause: vec![], } } pub fn either(&mut self, a: usize, b: usize) { assert!(a.min(!a) < self.size && b.min(!b) < self.size); self.clause.push((a, b)); } pub fn add_variable(&mut self) -> usize { let v = self.size; self.size += 1; v } pub fn at_most_one(&mut self, mut list: V) where V: Iterator + Clone, { let size = list.clone().count(); if size <= 1 { return; } let mut cur = !list.next().unwrap(); for v in list.clone().skip(1) { let next = self.add_variable(); self.either(cur, !v); self.either(cur, next); self.either(!v, next); cur = !next; } self.either(cur, !list.next().unwrap()); } pub fn solve(&self) -> Option> { let size = self.size; let g = CSR::new( 2 * size, self.clause.iter().flat_map(|&(a, b)| { let (x, ix) = if a >= size { (!a + size, !a) } else { (a, a + size) }; let (y, iy) = if b >= size { (!b + size, !b) } else { (b, b + size) }; assert!(x.max(ix).max(y).max(iy) < 2 * size); [(ix, y), (iy, x)] }), ); let (_, id) = strongly_connected_components(2 * size, |v| g.list(v)); let mut ans = Vec::with_capacity(size); for (a, b) in id.iter().zip(id[size..].iter()) { if *a == *b { return None; } else { ans.push(*a > *b); } } Some(ans) } } // ---------- end 2-SAT ---------- // ---------- begin CSR ---------- pub struct CSR { size: usize, pos: Vec, list: Vec, } impl CSR { pub fn new(size: usize, it: I) -> Self where I: Iterator + Clone, { let mut pos = vec![0; size + 1]; for (s, t) in it.clone() { assert!(s < size && t < size); pos[s + 1] += 1; } for i in 1..=size { pos[i] += pos[i - 1]; } let mut x = pos[..size].to_vec(); let mut list = vec![0; pos[size] as usize]; for (s, t) in it { let x = &mut x[s]; list[*x as usize] = t as u32; *x += 1; } CSR { size, pos, list } } pub fn list(&self, v: usize) -> impl Iterator + '_ { assert!(v < self.size); let s = self.pos[v] as usize; let t = self.pos[v + 1] as usize; self.list[s..t].iter().map(|p| *p as usize) } } // ---------- end CSR ---------- // ---------- begin strongry connected components ---------- pub fn strongly_connected_components(size: usize, graph: G) -> (usize, Vec) where G: Fn(usize) -> I, I: Iterator, { let mut ord = vec![0; size]; let mut res = vec![0; size]; let mut vertex = vec![]; let mut dfs = vec![]; let mut id = 0; for s in 0..size { if ord[s] > 0 { continue; } vertex.push(s); ord[s] = vertex.len(); dfs.push((s, graph(s))); while let Some((v, mut it)) = dfs.pop() { (|| { while let Some(u) = it.next() { if ord[u] == 0 { vertex.push(u); ord[u] = vertex.len(); dfs.push((v, it)); dfs.push((u, graph(u))); return; } } let low = graph(v).map(|u| ord[u]).min().unwrap_or(ord[v]); if low < ord[v] { ord[v] = low; return; } while let Some(u) = vertex.pop() { ord[u] = !0; res[u] = id; if u == v { break; } } id += 1; })(); } } res.iter_mut().for_each(|p| *p = id - 1 - *p); (id, res) } // ---------- end strongry connected components ---------- // ---------- begin enumerate prime ---------- fn enumerate_prime(n: usize, mut f: F) where F: FnMut(usize), { assert!(1 <= n && n <= 5 * 10usize.pow(8)); let batch = (n as f64).sqrt().ceil() as usize; let mut is_prime = vec![true; batch + 1]; for i in (2..).take_while(|p| p * p <= batch) { if is_prime[i] { let mut j = i * i; while let Some(p) = is_prime.get_mut(j) { *p = false; j += i; } } } let mut prime = vec![]; for (i, p) in is_prime.iter().enumerate().skip(2) { if *p && i <= n { f(i); prime.push(i); } } let mut l = batch + 1; while l <= n { let r = std::cmp::min(l + batch, n + 1); is_prime.clear(); is_prime.resize(r - l, true); for &p in prime.iter() { let mut j = (l + p - 1) / p * p - l; while let Some(is_prime) = is_prime.get_mut(j) { *is_prime = false; j += p; } } for (i, _) in is_prime.iter().enumerate().filter(|p| *p.1) { f(i + l); } l += batch; } } // ---------- end enumerate prime ----------