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 = sc.ne::() - 1; let x1 = sc.ne::() - 1; let y2 = sc.ne::() - 1; let x2 = 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 m = num.len(); let mut t = 0; for (_, val) in num.iter_mut() { *val = t; t += 1; } let mut adj = vec![Vec::new(); n + m]; for i in 0..n { let u = num[&edge[i].0]; let v = num[&edge[i].1]; adj[i].push(n + u); adj[i].push(n + v); adj[n + u].push(i); adj[n + v].push(i); } let ans = match bimatch(&adj, n) { val if val == n => "YES", _ => "NO", }; println!("{}", ans); } fn bimatch(adj: &Vec>, ln: usize) -> usize { fn dfs(cur: usize, adj: &Vec>, mut match_to: &mut Vec>, mut used: &mut Vec) -> bool { for &nxt in &adj[cur] { if used[nxt] { continue; } used[nxt] = true; let assign = match match_to[nxt] { Some(v) => dfs(v, &adj, &mut match_to, &mut used), None => true, }; if assign { match_to[cur] = Some(nxt); match_to[nxt] = Some(cur); return true; } } false } let n = adj.len(); let mut match_to: Vec> = vec![None; n]; let mut res = 0; for i in 0..ln { if match_to[i] != None { continue; } let mut used = vec![false; n]; if dfs(i, &adj, &mut match_to, &mut used) { res += 1; } } res } fn main() { const DEFAULT_STACK: usize = 16 * 1024 * 1024; 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() } }