#![allow(dead_code)] #![allow(unused_imports)] #![allow(unused_macros)] use std::cmp::*; use std::fmt::*; use std::hash::*; use std::io::BufRead; use std::iter::FromIterator; use std::*; use std::{cmp, collections, fmt, io, iter, ops, str}; const INF: i64 = 1223372036854775807; const UINF: usize = INF as usize; const LINF: i64 = 2147483647; const INF128: i128 = 1223372036854775807000000000000; const MOD1: i64 = 1000000007; const MOD9: i64 = 998244353; const MOD: i64 = MOD9; const UMOD: usize = MOD as usize; const M_PI: f64 = 3.14159265358979323846; use cmp::Ordering::*; use std::collections::*; use std::io::stdin; use std::io::stdout; use std::io::Write; macro_rules! p { ($x:expr) => { println!("{}", $x); }; } macro_rules! vp { ($x:expr) => { println!( "{}", $x.iter() .map(|x| x.to_string()) .collect::<Vec<_>>() .join(" ") ); }; } macro_rules! d { ($x:expr) => { eprintln!("{:?}", $x); }; } macro_rules! yn { ($val:expr) => { if $val { println!("Yes"); } else { println!("No"); } }; } macro_rules! map{ ($($key:expr => $val:expr),*) => { { let mut map = ::std::collections::BTreeMap::new(); $( map.insert($key, $val); )* map } }; } macro_rules! set{ ($($key:expr),*) => { { let mut set = ::std::collections::BTreeSet::new(); $( set.insert($key); )* set } }; } #[allow(dead_code)] fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } #[allow(dead_code)] fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[allow(dead_code)] fn read_mat<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> { (0..n).map(|_| read_vec()).collect() } #[allow(dead_code)] fn readii() -> (i64, i64) { let mut vec: Vec<i64> = read_vec(); (vec[0], vec[1]) } #[allow(dead_code)] fn readiii() -> (i64, i64, i64) { let mut vec: Vec<i64> = read_vec(); (vec[0], vec[1], vec[2]) } #[allow(dead_code)] fn readuu() -> (usize, usize) { let mut vec: Vec<usize> = read_vec(); (vec[0], vec[1]) } #[allow(dead_code)] fn readff() -> (f64, f64) { let mut vec: Vec<f64> = read_vec(); (vec[0], vec[1]) } fn readcc() -> (char, char) { let mut vec: Vec<char> = read_vec(); (vec[0], vec[1]) } fn readuuu() -> (usize, usize, usize) { let mut vec: Vec<usize> = read_vec(); (vec[0], vec[1], vec[2]) } #[allow(dead_code)] fn readiiii() -> (i64, i64, i64, i64) { let mut vec: Vec<i64> = read_vec(); (vec[0], vec[1], vec[2], vec[3]) } #[allow(dead_code)] fn readuuuu() -> (usize, usize, usize, usize) { let mut vec: Vec<usize> = read_vec(); (vec[0], vec[1], vec[2], vec[3]) } //derive clone #[derive(Clone)] struct E { to: usize, p: u8, } fn main() { let m: usize = read(); let mut t = vec![]; for _ in 0..m { let v: Vec<u32> = read_vec(); t.push((v[0], v[1], v[2])); } let mut e = HashMap::new(); for (i, &(a, b, c)) in t.iter().enumerate() { let edges = vec![((a, b), 0u8), ((a, c), 1u8), ((b, c), 0u8)]; for ((u, v), f) in edges { e.entry((u, v)).or_insert(vec![]).push((i, f)); } } let mut g = vec![vec![]; m]; for (_, v) in e { if v.len() > 2 { p!("NO"); return; } if v.len() == 2 { let (t1, f1) = v[0]; let (t2, f2) = v[1]; let p = 1 ^ (f1 ^ f2); g[t1].push(E { to: t2, p }); g[t2].push(E { to: t1, p }); } } let mut c = vec![None; m]; //0の渦の隣には1が隣接してなければならない三角形を単位にして二部グラフ判定をする。 for i in 0..m { if c[i].is_none() { let mut q = VecDeque::new(); c[i] = Some(0); q.push_back(i); while let Some(u) = q.pop_front() { let cu = c[u].unwrap(); for e in &g[u] { let v = e.to; let r = cu ^ e.p; if let Some(cv) = c[v] { if cv != r { p!("NO"); return; } } else { c[v] = Some(r); q.push_back(v); } } } } } p!("YES"); }