struct DSU {
par: Vec<usize>,
siz: Vec<usize>,
}
impl DSU {
fn new(n: usize) -> Self {
Self {
par: (0..n).collect(),
siz: vec![1; n],
}
}
fn root(&mut self, u: usize) -> usize {
if self.par[u] == u {
u
} else {
self.par[u] = self.root(self.par[u]);
self.par[u]
}
}
fn unite(&mut self, mut u: usize, mut v: usize) {
u = self.root(u);
v = self.root(v);
if u == v {
return;
}
if self.siz[u] > self.siz[v] {
self.par[v] = u;
self.siz[u] += self.siz[v];
} else {
self.par[u] = v;
self.siz[v] += self.siz[u];
}
}
fn same(&mut self, u: usize, v: usize) -> bool {
self.root(u) == self.root(v)
}
fn size(&mut self, u: usize) -> usize {
let r = self.root(u);
self.siz[r]
}
}