use std::cmp::Ordering; use std::cmp; use std::cmp::min; use std::collections::BTreeMap; use std::process; use std::cmp::Ord; use std::collections::HashMap; use std::collections::HashSet; use std::collections::VecDeque; use std::collections::BTreeSet; use std::mem; use std::collections::BinaryHeap; use std::hash::{Hash, Hasher}; pub struct Scanner { stdin: R, } impl Scanner { pub fn read(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r') .collect::>(); std::str::from_utf8(&buf).unwrap() .parse() .ok() .expect("Parse error.") } pub fn vec(&mut self, n: usize) -> Vec { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec { self.read::().chars().collect() } } pub trait BinarySearch { fn lower_bound(&self, x:&T) -> usize; fn upper_bound(&self, x:&T) -> usize; } impl BinarySearch for VecDeque{ 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 } } 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 } } fn comb(a:usize, b:usize, fac:&Vec, ifac:&Vec)->usize{ let mut a = a; let mut b = b; if a == 0 && b == 0{return 1;} if a, ifac:&Vec)->usize{ return comb(n+r-1, r, fac, ifac); } fn modinv(a:usize, M:usize)->usize{ let mut b = M as i64; let mut u = 1 as i64; let mut v = 0 as i64; let mut a = a as i64; let mut m = M as i64; while(b>0){ let mut t = a/b; a -= t*b; mem::swap(&mut a, &mut b); u-=t*v; mem::swap(&mut u, &mut v); } u%=m; if u<0{u+=m;} return u as usize; } fn modpow(x:usize, n:usize) -> usize{ let mut ans = 1; let mut n = n as usize; let mut x = x; while(n != 0){ if (n&1 == 1){ans = ans*x%MODu;} x = x*x%MODu; n = n>>1; } ans } fn invs(max:usize)->(Vec, Vec){ let mut fac = vec![0;max+1]; let mut ifac = vec![0;max+1]; fac[0] = 1; ifac[0] = 1; for i in 0..max{ fac[i+1] = fac[i] * (i+1)%MODu; ifac[i+1] = ifac[i] * modpow(i+1, MODu - 2)%MODu; } (fac, ifac) } fn solve(){ let sssss = std::io::stdin(); let mut sc = Scanner { stdin: sssss.lock() }; let mut N:usize = sc.read(); let mut M:usize = sc.read(); let mut g = vec![vec![];N]; let mut g2 = g.clone(); let mut h = vec![0usize;N]; for i in 0..M{ let mut u:usize = sc.read(); let mut v:usize = sc.read(); u-=1; v-=1; g[u].push(v); h[v]+=1; g2[u].push(v); g2[v].push(u); } let mut zeros = vec![]; for i in 0..N{ if h[i] == 0{ zeros.push(i); } } fn dfs(s:usize, used:&mut Vec, vs:&mut HashSet, g:&Vec>){ if used[s]{ return; } used[s] = true; vs.insert(s); for i in &g[s]{ dfs(*i, used, vs, g); } } let mut used = vec![false;N]; let mut res= vec![]; let mut u = HashSet::new(); for i in zeros{ if used[i] == false{ let mut vs = HashSet::new(); dfs(i, &mut used, &mut vs, &g2); let mut vs:Vec = vs.into_iter().collect(); let mut st = vec![]; let mut tmp = vec![]; for j in 0..vs.len(){ if h[vs[j]] == 0{ st.push(vs[j]); } } while(st.len() != 0){ let mut i = st.pop().unwrap(); tmp.push(i); for j in &g[i]{ h[*j]-=1; if h[*j] == 0{ st.push(*j); } } } let mut ok = true; for j in 0..vs.len(){ if h[vs[j]] != 0{ ok = false; } } if ok{ for j in 0..tmp.len()-1{ res.push(vec![tmp[j], tmp[j+1]]); } } else{ for x in vs{ u.insert(x); } } } } let mut u:Vec = u.into_iter().collect(); for i in 0..u.len(){ res.push(vec![u[i], u[(i+1)%u.len()]]); } println!("{}", res.len()); for i in 0..res.len(){ println!("{} {}", res[i][0]+1, res[i][1]+1); } } fn main(){ solve(); } const PI:f64 = std::f64::consts::PI; pub static MOD:i64 = 1000000007; pub static MODu:usize = 998244353; pub static MODi32:i32 = 1000000007; pub static eps:f64 = 1e-6; const INF: i64 = 1 << 60; const INFu:usize = 1<<56; const INFu128:u128 = 1<<126;