// -*- coding:utf-8-unix -*- // #![feature(map_first_last)] #![allow(dead_code)] #![allow(unused_imports)] #![allow(unused_macros)] use std::arch::x86_64::_XCR_XFEATURE_ENABLED_MASK; use std::cmp::Ordering::*; use std::collections::*; use std::convert::*; use std::convert::{From, Into}; use std::f64::consts::PI; use std::fmt::Debug; use std::fmt::Display; use std::fs::File; use std::hash::Hash; use std::io::prelude::*; use std::io::*; use std::marker::Copy; use std::mem::*; use std::ops::Bound::*; use std::ops::{Add, Mul, Neg, Sub}; use std::str; use std::vec; use std::{cmp, process::Output}; use std::{cmp::Ordering, env::consts::DLL_PREFIX}; const INF: i64 = 1223372036854775807; const UINF: usize = INF as usize; // const FINF: f64 = 122337203685.0; const LINF: i64 = 2147483647; const FINF: f64 = LINF as f64; const INF128: i128 = 1223372036854775807000000000000; const MOD: i64 = 1000000007; // const MOD: i64 = 998244353; const MPI: f64 = 3.14159265358979323846264338327950288f64; // const MOD: i64 = INF; const UMOD: usize = MOD as usize; use std::cmp::*; use std::collections::*; use std::io::stdin; use std::io::stdout; use std::io::Write; macro_rules! p { ($x:expr) => { println!("{}", $x); }; } macro_rules! d { ($x:expr) => { println!("{:?}", $x); }; } macro_rules! chmin { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_min = min!($($cmps),+); if $base > cmp_min { $base = cmp_min; true } else { false } }}; } macro_rules! chmax { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_max = max!($($cmps),+); if $base < cmp_max { $base = cmp_max; true } else { false } }}; } macro_rules! min { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::min($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::min($a, min!($($rest),+)) }}; } macro_rules! max { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::max($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::max($a, max!($($rest),+)) }}; } // use str::Chars; // use str::Chars; #[allow(dead_code)] fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } #[allow(dead_code)] fn readi() -> (i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); iter.next().unwrap().parse::().unwrap() } #[allow(dead_code)] fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[allow(dead_code)] fn read_mat(n: u32) -> Vec> { (0..n).map(|_| read_vec()).collect() } #[allow(dead_code)] fn readii() -> (i64, i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } fn readff() -> (f64, f64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readiii() -> (i64, i64, i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readuu() -> (usize, usize) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } fn readcc() -> (char, char) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readuuu() -> (usize, usize, usize) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readuuuu() -> (usize, usize, usize, usize) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } fn readiiii() -> (i64, i64, i64, i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } pub mod dinic { #[derive(Clone, Copy, Debug)] struct Edge { to: usize, cap: i64, rev: usize, } pub struct Network { g: Vec>, level: Vec>, iter: Vec, } #[doc = "direct flow graph. O(EV^2)"] impl Network { pub fn new(n: usize) -> Network { Network { g: vec![vec![]; n], level: vec![None; n], iter: vec![0; n], } } pub fn add_edge(&mut self, from: usize, to: usize, cap: i64) { assert!(cap >= 0); let from_rev = self.g[to].len(); let to_rev = self.g[from].len(); self.g[from].push(Edge { to: to, cap: cap, rev: from_rev, }); self.g[to].push(Edge { to: from, cap: 0, rev: to_rev, }); } fn n(&self) -> usize { self.g.len() } fn bfs(&mut self, s: usize) { self.level = vec![None; self.n()]; let mut q = std::collections::VecDeque::new(); q.push_back(s); self.level[s] = Some(0); while let Some(v) = q.pop_front() { for e in &self.g[v] { if e.cap > 0 && self.level[e.to].is_none() { self.level[e.to] = self.level[v].map(|x| x + 1); q.push_back(e.to); } } } } fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 { if v == t { return f; } let iter_v_cur = self.iter[v]; for i in iter_v_cur..self.g[v].len() { let e = self.g[v][i].clone(); if e.cap > 0 && self.level[v] < self.level[e.to] { let d = self.dfs(e.to, t, std::cmp::min(f, e.cap)); if d > 0 { self.g[v][i].cap -= d; self.g[e.to][e.rev].cap += d; return d; } } self.iter[v] += 1; } return 0; } pub fn max_flow(&mut self, s: usize, t: usize) -> i64 { let mut flow = 0; loop { self.bfs(s); // finally if we could not find any path to t then return flow if self.level[t].is_none() { return flow; } let INF = 2_000_000_001; self.iter = vec![0; self.n()]; let mut f = self.dfs(s, t, INF); while f > 0 { flow += f; f = self.dfs(s, t, INF); } } } } } // #[test] // fn test_dinic() { // use dinic::*; // let mut nw = Network::new(5); // let conns = [ // (0, 1, 10), // (0, 2, 2), // (1, 2, 6), // (1, 3, 6), // (3, 2, 3), // (2, 4, 5), // (3, 4, 8), // ]; // for conn in &conns { // nw.add_edge(conn.0, conn.1, conn.2); // } // assert_eq!(nw.max_flow(0, 4), 11); // } /// Equivalent to std::lowerbound and std::upperbound in c++ pub trait BinarySearch { fn lower_bound(&self, x: &T) -> usize; fn upper_bound(&self, x: &T) -> usize; } impl BinarySearch for [T] { fn lower_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less => { low = mid + 1; } Ordering::Equal | Ordering::Greater => { high = mid; } } } low } fn upper_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less | Ordering::Equal => { low = mid + 1; } Ordering::Greater => { high = mid; } } } low } } #[derive(PartialEq, Eq, Clone, Debug)] enum Inf { Val(T), Inf, } impl Inf { #[allow(dead_code)] fn val(self) -> Option { match self { Inf::Val(v) => Some(v), _ => None, } } } impl PartialOrd for Inf { fn partial_cmp(&self, other: &Self) -> Option { match (self, other) { (&Inf::Inf, &Inf::Inf) => Some(Ordering::Equal), (&Inf::Inf, &Inf::Val(_)) => Some(Ordering::Greater), (&Inf::Val(_), &Inf::Inf) => Some(Ordering::Less), (&Inf::Val(ref a), &Inf::Val(ref b)) => a.partial_cmp(b), } } } impl Ord for Inf { fn cmp(&self, other: &Self) -> Ordering { match (self, other) { (&Inf::Inf, &Inf::Inf) => Ordering::Equal, (&Inf::Inf, &Inf::Val(_)) => Ordering::Greater, (&Inf::Val(_), &Inf::Inf) => Ordering::Less, (&Inf::Val(ref a), &Inf::Val(ref b)) => a.cmp(b), } } } #[allow(dead_code)] /// Calculate length of Longest Increasing Subsequence. O(N log N) pub fn lis(seq: &[T]) -> Vec> { let mut dp: Vec> = vec![Inf::Inf; seq.len() + 1]; for x in seq.iter() { let i = dp.lower_bound(&Inf::Val(x)); dp[i] = Inf::Val(x); } let mut res = vec![]; for i in dp { if i != Inf::Inf { res.push(i.val()); } } return res; } fn solve() { use dinic::*; let (n, m, q) = readuuu(); let mut data = vec![]; for i in 0..q { let (a, b) = readuu(); data.push((b, a)); } // data.sort(); for i in 0..data.len() { data[i] = (data[i].1, data[i].0); } let li = lis(&data); // d!(li); // println!("{:?}", li); let mut st = BTreeSet::new(); for i in li { st.insert(i.unwrap().1); } println!("{:?}", st.len()); // let mut nw = Network::new(n + m + 2); // // let conns = [ // // (0, 1, 10), // // (0, 2, 2), // // (1, 2, 6), // // (1, 3, 6), // // (3, 2, 3), // // (2, 4, 5), // // (3, 4, 8), // // ]; // let mut conns = vec![(0, 0, 0); 0]; // let mut src = 0; // let mut dst = n + m + 1; // for i in 0..n { // conns.push((src, i + 1, 1)); // } // for i in 0..m { // conns.push((i + 1 + n, dst, 1)); // } // for i in 0..q { // let (a, b) = readuu(); // if a >= b { // continue; // } // conns.push((a, n + b, 1)); // } // for conn in &conns { // nw.add_edge(conn.0, conn.1, conn.2); // } // let mut res = nw.max_flow(src, dst); // println!("{:?}", res); return; } fn main() { solve(); return; }