use std::io::{self, Stdin}; use std::str::{self, FromStr}; use std::error::Error; use std::thread; use std::collections::*; fn exec() { let mut sc = Scanner::new(); let n: usize = sc.ne(); let mut edge = vec![(0, 0); n]; let mut num = BTreeMap::new(); for i in 0..n { let y1: usize = sc.ne::() - 1; let x1: usize = sc.ne::() - 1; let y2: usize = sc.ne::() - 1; let x2: usize = sc.ne::() - 1; let n1 = y1 * 100 + x1; let n2 = y2 * 100 + x2; edge[i] = (n1, n2); num.insert(n1, 0); num.insert(n2, 0); } let mut t = 0; for (_, val) in num.iter_mut() { *val = t; t += 1; } let m = num.len(); let mut uf = UnionFind::new(m); for &(u_, v_) in &edge { let u = num[&u_]; let v = num[&v_]; uf.unite(u, v); } let mut cnt = vec![0; m]; for &(u_, _) in &edge { let u = num[&u_]; cnt[uf.root(u)] += 1; } let mut ok = true; for i in 0..m { if uf.root(i) == i { ok &= cnt[i] <= uf.size(i); } } println!("{}", if ok { "YES" } else { "NO" }); } struct UnionFind { data: Vec, group: usize, } #[allow(dead_code)] impl UnionFind { fn new(n: usize) -> UnionFind { UnionFind { data: vec![-1i32; n], group: n, } } //経路圧縮のみ fn unite(&mut self, x: usize, y: usize) -> bool { let x = self.root(x); let y = self.root(y); if x == y { return false; } self.data[x] += self.data[y]; self.data[y] = x as i32; self.group -= 1; true } fn root(&mut self, x: usize) -> usize { if self.data[x] < 0 { x } else { let par = self.data[x] as usize; let res = self.root(par); self.data[x] = res as i32; res } } fn same(&mut self, x: usize, y: usize) -> bool { self.root(x) == self.root(y) } fn size(&mut self, x: usize) -> i32 { let par = self.root(x); -self.data[par] } } const DEFAULT_STACK: usize = 16 * 1024 * 1024; fn main() { let builder = thread::Builder::new(); let th = builder.stack_size(DEFAULT_STACK); let handle = th.spawn(|| { exec(); }).unwrap(); let _ = handle.join(); } #[allow(dead_code)] struct Scanner { stdin: Stdin, id: usize, buf: Vec, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { stdin: io::stdin(), id: 0, buf: Vec::new(), } } fn next_line(&mut self) -> Option { let mut res = String::new(); match self.stdin.read_line(&mut res) { Ok(0) => return None, Ok(_) => Some(res), Err(why) => panic!("error in read_line: {}", why.description()), } } fn next(&mut self) -> Option { while self.buf.len() == 0 { self.buf = match self.next_line() { Some(r) => { self.id = 0; r.trim().as_bytes().to_owned() } None => return None, }; } let l = self.id; assert!(self.buf[l] != b' '); let n = self.buf.len(); let mut r = l; while r < n && self.buf[r] != b' ' { r += 1; } let res = match str::from_utf8(&self.buf[l..r]).ok().unwrap().parse::() { Ok(s) => Some(s), Err(_) => panic!("parse error"), }; while r < n && self.buf[r] == b' ' { r += 1; } if r == n { self.buf.clear(); } else { self.id = r; } res } fn ne(&mut self) -> T { self.next::().unwrap() } }