// -*- coding:utf-8-unix -*- // #![feature(map_first_last)] #![allow(dead_code)] #![allow(unused_imports)] #![allow(unused_macros)] use std::collections::*; use std::convert::*; use std::convert::{From, Into}; use std::fmt::Debug; use std::fs::File; 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::thread::park_timeout; use std::vec; use std::{cmp, process::Output}; use std::{cmp::Ordering, env::consts::DLL_PREFIX}; use std::{cmp::Ordering::*, f32::consts::PI}; const INF: i64 = 1223372036854775807; const UINF: usize = INF as usize; const FINF: f64 = 122337203685.0; const INF128: i128 = 1223372036854775807000000000000; const LINF: i64 = 2147483647; const MOD: i64 = 1000000007; // const MOD: i64 = 998244353; // 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! dd { (x:expr) => { dbg!(x); }; } // 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_vec2(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 struct SEG { n: usize, buf: Vec, } impl SEG { #[allow(dead_code)] pub fn new(n: usize) -> SEG { SEG { n, buf: vec![M::id(); 2 * n], } } #[allow(dead_code)] pub fn update(&mut self, k: usize, a: M::T) { let mut k = k + self.n; self.buf[k] = a; while k > 0 { k >>= 1; self.buf[k] = M::op(&self.buf[k << 1], &self.buf[(k << 1) | 1]); } } #[allow(dead_code)] pub fn add(&mut self, k: usize, a: &M::T) { let mut k = k + self.n; self.buf[k] = M::op(&self.buf[k], a); while k > 0 { k >>= 1; self.buf[k] = M::op(&self.buf[k << 1], &self.buf[(k << 1) | 1]); } } #[allow(dead_code)] pub fn get(&self, i: usize) -> M::T { self.query(i, i + 1) } #[allow(dead_code)] pub fn query_range>(&self, range: R) -> M::T { let l = match range.start_bound() { std::ops::Bound::Excluded(&x) => { assert!(x > 0); x - 1 } std::ops::Bound::Included(&x) => x, std::ops::Bound::Unbounded => 0, }; let r = match range.end_bound() { std::ops::Bound::Excluded(&x) => x, std::ops::Bound::Included(&x) => (x + 1), std::ops::Bound::Unbounded => self.n, }; self.query(l, r) } #[allow(dead_code)] pub fn query(&self, l: usize, r: usize) -> M::T { let mut vl = M::id(); let mut vr = M::id(); let mut l = l + self.n; let mut r = r + self.n; while l < r { if l & 1 == 1 { vl = M::op(&vl, &self.buf[l]); l += 1; } if r & 1 == 1 { r -= 1; vr = M::op(&self.buf[r], &vr); } l >>= 1; r >>= 1; } M::op(&vl, &vr) } } pub trait Monoid { type T: Clone; fn id() -> Self::T; fn op(a: &Self::T, b: &Self::T) -> Self::T; } pub enum MON {} impl Monoid for MON { type T = usize; fn id() -> Self::T { 1 } fn op(a: &Self::T, b: &Self::T) -> Self::T { *a * *b } } fn vector_compression(vec: &mut Vec) -> Vec { let n = vec.len(); let mut res = vec![0; n]; let mut bt = BTreeMap::new(); for i in 0..n { *bt.entry(vec[i]).or_insert(1) += 1; } let mut bt2 = BTreeMap::new(); let mut cnt: usize = 0; for i in bt { bt2.insert(i.0, cnt); cnt += 1; } for i in 0..n { // let mut xx: usize = vec[i]; res[i] = *bt2.get(&(vec[i])).unwrap(); } return res; } fn solve() { let (n, m) = readuu(); let mut vp = vec![(0, 0); 0]; let mut vec = vec![]; for i in 0..m { let (a, b) = readuu(); vec.push(b); vec.push(a); } let vec = vector_compression(&mut vec); for i in 0..m { vp.push((vec[2 * i], vec[2 * i + 1])); } vp.sort(); // println!("{:?}", vp.clone()); let mut seg: SEG = SEG::new(201010); let mut res = n; for i in 0..m { let p = vp[i].0; let x = seg.query(vp[i].1, vp[i].0 + 1); if x != 0 { seg.update(p, 0); res -= 1; } } println!("{:?}", res); return; } fn main() { solve(); }