fn main() { let (n, m): (usize, usize) = get::tuple(); let edges: Vec<(usize, usize)> = get::tuples(m); let mut freq = vec![false; n]; for &(a, b) in &edges { freq[a] = true; freq[b] = true; } let map = freq.iter().scan(0,|a,&x| {if x {*a+=1; Some(*a)} else {Some(0)}}).collect::>(); let edges = edges.iter().map(|&(a,b)| (map[a]-1,map[b]-1)).collect::>(); let n = freq.iter().filter(|&&p|p).count(); let g = Graph::new_nonlabeled(n, &edges); if Graph::is_hitofude(&g) && Graph::is_connected(&g) { println!("YES"); } else { println!("NO"); } } struct Graph { size: usize, adj: Vec> } impl Clone for Graph { fn clone(&self) -> Graph { Graph { size: self.size, adj: self.adj.clone() } } } #[allow(dead_code)] impl Graph { fn new_nonlabeled(n: usize, edges: &[(usize, usize)]) -> Graph { let edges = edges.iter().map(|&(a,b)|(a,b,0isize)).collect::>(); Graph::new_labeled(n, &edges) } fn new_labeled(n: usize, edges: &[(usize, usize, isize)]) -> Graph { let mut g: Vec> = vec![vec![]; n]; for &(a, b, c) in edges { g[a].push((b,c)); g[b].push((a,c)); // delete for digraph } Graph {size: n, adj: g} } fn is_connected(&self) -> bool { self.dfs(0).len() == self.size } fn size(&self) -> usize { self.size } fn edges(&self) -> Vec<(usize, usize, isize)> { let mut buf = vec![]; for (i, next) in self.adj.iter().enumerate() { for &(j, x) in next { buf.push((i, j, x)) } } buf } fn is_hitofude(&self) -> bool { let ploop = self.adj.iter().all(|vs|vs.len()%2==0); let pnloop = self.adj.iter().filter(|vs|vs.len()%2==1).count() == 2; ploop || pnloop } fn bellman_ford(&self, s: usize) -> Vec { const INF: isize = std::isize::MAX >> 1; let edges = self.edges(); let mut bf: Vec = vec![INF; self.size]; bf[s] = 0; for _ in 1 .. self.size { for &(v, w, c) in &edges { bf[w] = std::cmp::min(bf[w], bf[v]+c) } } bf } fn dijkstra(&self, s: usize) -> Vec { use std::collections::BinaryHeap; const INF: isize = std::isize::MAX; let mut dk: Vec = vec![INF; self.size]; dk[s] = 0; let mut pq = BinaryHeap::new(); pq.push((0,s)); while let Some((acc,v)) = pq.pop() { let acc = -acc; for &(w,c) in &self.adj[v] { let cand = acc + c; if cand < dk[w] { dk[w] = cand; pq.push((-cand,w)); } } } dk } fn warshall_floyd(&self) -> Vec> { const INF: isize = std::isize::MAX >> 1; let mut wf: Vec> = vec![vec![INF; self.size]; self.size]; for i in 0 .. self.size {wf[i][i] = 0} for (i, next) in self.adj.iter().enumerate() { for &(j, x) in next { wf[i][j] = x } } for k in 0 .. self.size { for i in 0 .. self.size { for j in 0 .. self.size { wf[i][j] = std::cmp::min(wf[i][j], wf[i][k] + wf[k][j]); } } } wf } fn coloring2(&self) -> Option<(Vec, Vec)> { fn paint(v: usize, p: bool, g: &Graph, cv: &mut Vec>) -> bool { match cv[v] { None => { let next = &g.adj[v]; cv[v] = Some(p); next.iter().all(|&(w,_)|paint(w,!p,g,cv))}, Some(q) => {q == p} } } let mut canvas: Vec> = vec![None; self.size]; let ans = paint(0, false, self, &mut canvas); let bs = canvas.iter().enumerate().filter(|&(_,&v)|v==Some(false)).map(|(i,_)|i).collect::>(); let ws = canvas.iter().enumerate().filter(|&(_,&v)|v==Some(true)).map(|(i,_)|i).collect::>(); if ans {Some((bs,ws))} else {None} } fn dfs(&self, s: usize) -> Vec { fn go(g: &Graph, current: usize, mut path: &mut Vec, mut visited: &mut Vec) { for &(next, _) in &g.adj[current] { if visited[next] { continue } else { visited[next] = true; path.push(next); go(&g, next, &mut path, &mut visited) } } } let mut path = vec![s]; let mut visited = vec![false; self.adj.len()]; visited[s] = true; go(&self, s, &mut path, &mut visited); path } fn cut(&mut self, v: usize, w: usize) { self.adj[v].retain(|&(t,_)| t != w); self.adj[w].retain(|&(t,_)| t != v); } } #[allow(dead_code)] mod get { use std::io::*; use std::str::*; pub fn val() -> T { let mut buf = String::new(); stdin().read_line(&mut buf).ok(); buf.trim().parse::().ok().unwrap() } pub fn vals(n: usize) -> Vec { let mut vec: Vec = vec![]; for _ in 0 .. n { vec.push(val()); } vec } pub fn tuple() -> (T1, T2) { let mut buf = String::new(); stdin().read_line(&mut buf).ok(); let mut it = buf.trim().split_whitespace(); let x = it.next().unwrap().parse::().ok().unwrap(); let y = it.next().unwrap().parse::().ok().unwrap(); (x, y) } pub fn tuples(n: usize) -> Vec<(T1, T2)> { let mut vec: Vec<(T1, T2)> = vec![]; for _ in 0 .. n { vec.push(tuple()); } vec } pub fn tuple3() -> (T1, T2, T3) { let mut buf = String::new(); stdin().read_line(&mut buf).ok(); let mut it = buf.trim().split_whitespace(); let x = it.next().unwrap().parse::().ok().unwrap(); let y = it.next().unwrap().parse::().ok().unwrap(); let z = it.next().unwrap().parse::().ok().unwrap(); (x, y, z) } pub fn tuple3s(n: usize) -> Vec<(T1, T2, T3)> { let mut vec: Vec<(T1, T2, T3)> = vec![]; for _ in 0 .. n { vec.push(tuple3()); } vec } pub fn list() -> Vec { let mut buf = String::new(); stdin().read_line(&mut buf).ok(); buf.trim().split_whitespace().map(|t| t.parse::().ok().unwrap()).collect() } pub fn lists(h: usize) -> Vec> { let mut mat: Vec> = vec![]; for _ in 0 .. h { mat.push(list()); } mat } }