#[derive(Debug)]
struct Bijection {
  n: usize,
  map: Vec<Option<usize>>,
  inv: Vec<Option<usize>>
}

#[allow(dead_code)]
impl Bijection {
  fn new(f: &[(usize, usize)]) -> Bijection {
    use std::collections::HashSet;
    
    let dom = f.iter().map(|f|f.0).collect::<HashSet<_>>();
    let img = f.iter().map(|f|f.1).collect::<HashSet<_>>();
    assert!(dom.len() == f.len());
    assert!(img.len() == f.len());

    let max_dom = dom.iter().max().unwrap();
    let max_img = img.iter().max().unwrap();
    let mut map = vec![None; max_dom+1];
    let mut inv = vec![None; max_img+1];
    for &(x, y) in f {
      map[x] = Some(y);
      inv[y] = Some(x)
    }
    
    Bijection{n: f.len(), map: map, inv: inv}
  }
  
  fn swap_dom(&mut self, x1: usize, x2: usize) {
    assert!(self.map[x1].is_some());
    assert!(self.map[x2].is_some());
    let y1 = self.map[x1].unwrap();
    let y2 = self.map[x2].unwrap();
    self.map.swap(x1, x2);
    self.inv.swap(y1, y2)
  }
  
  fn swap_img(&mut self, y1: usize, y2: usize) {
    assert!(self.inv[y1].is_some());
    assert!(self.inv[y2].is_some());
    let x1 = self.inv[y1].unwrap();
    let x2 = self.inv[y2].unwrap();
    self.inv.swap(y1, y2);
    self.map.swap(x1, x2)
  }
  
  fn print(&self) {
    for (x, &opty) in self.map.iter().enumerate() {
      if let Some(y) = opty {println!("{} {}", x, y)}
    }
  }
}