pub const UNION_FIND_SRC: &'static str = "// #region UnionFind\nuse std::collections::HashMap;\n\npub struct UnionFind4Usize {\n id: Vec<usize>,\n size: Vec<usize>,\n count: usize,\n length: usize,\n}\n\npub struct UnionFind<T>\nwhere\n T: std::cmp::Eq,\n T: std::hash::Hash,\n T: std::fmt::Debug,\n{\n map: HashMap<T, usize>,\n uf: UnionFind4Usize,\n}\n\nimpl UnionFind4Usize {\n pub fn new(count: usize) -> Self {\n UnionFind4Usize {\n count,\n length: count,\n id: (0..count).collect(),\n size: vec![1; count as usize],\n }\n }\n\n pub fn add(&mut self) -> usize {\n self.count += 1;\n self.id.push(self.length);\n self.size.push(1);\n self.length += 1;\n self.length - 1\n }\n\n pub fn is_connected(&mut self, p: usize, q: usize) -> bool {\n self.find(p) == self.find(q)\n }\n\n pub fn find(&mut self, p: usize) -> usize {\n let mut p = p;\n while p != self.id[p] {\n self.id[p] = self.id[self.id[p]];\n p = self.id[p]\n }\n p\n }\n\n pub fn union(&mut self, p: usize, q: usize) {\n let i = self.find(p);\n let j = self.find(q);\n if i == j {\n return;\n }\n if self.size[i] < self.size[j] {\n self.id[i] = j;\n self.size[j] += self.size[i];\n } else {\n self.id[j] = i;\n self.size[i] += self.size[j];\n }\n self.count -= 1;\n }\n\n pub fn union_count(&self) -> usize {\n self.count\n }\n\n pub fn union_size(&mut self, p: usize) -> usize {\n let root = self.find(p);\n return self.size[root];\n }\n\n pub fn len(&self) -> usize {\n self.length\n }\n}\n\nimpl<T> UnionFind<T>\nwhere\n T: std::cmp::Eq,\n T: std::hash::Hash,\n T: std::fmt::Debug,\n{\n pub fn new() -> Self {\n UnionFind {\n map: HashMap::new(),\n uf: UnionFind4Usize {\n count: 0,\n length: 0,\n id: Vec::new(),\n size: Vec::new(),\n },\n }\n }\n\n pub fn from_iter<I>(iter: I) -> UnionFind<T>\n where\n I: IntoIterator<Item = T>,\n {\n let mut map = HashMap::new();\n let mut index = 0;\n for item in iter.into_iter() {\n map.insert(item, index);\n index += 1;\n }\n let len = map.len();\n UnionFind {\n map,\n uf: UnionFind4Usize::new(len),\n }\n }\n\n pub fn len(&self) -> usize {\n self.uf.len()\n }\n\n pub fn union_count(&self) -> usize {\n self.uf.union_count()\n }\n\n pub fn union_size(&mut self, p: T) -> Option<usize> {\n if let Some(index) = self.map.get(&p) {\n let root_index = self.uf.find(*index);\n Some(self.uf.union_size(root_index))\n } else {\n None\n }\n }\n\n pub fn find(&mut self, p: T) -> Option<&T> {\n if let Some(index) = self.map.get(&p) {\n let root_index = self.uf.find(*index);\n self._find_by_index(root_index)\n } else {\n None\n }\n }\n\n pub fn union(&mut self, p: T, q: T) -> Result<usize, String> {\n if let Some(pindex) = self.map.get(&p) {\n if let Some(qindex) = self.map.get(&q) {\n self.uf.union(*pindex, *qindex);\n return Ok(self.uf.union_size(*pindex));\n } else {\n return Err(format!(\"{:?} not found.\", q));\n }\n } else {\n return Err(format!(\"{:?} not found.\", p));\n }\n }\n\n pub fn is_connected(&mut self, p: T, q: T) -> Result<bool, String> {\n if let Some(pindex) = self.map.get(&p) {\n if let Some(qindex) = self.map.get(&q) {\n return Ok(self.uf.find(*pindex) == self.uf.find(*qindex));\n } else {\n return Err(format!(\"{:?} not found.\", q));\n }\n } else {\n return Err(format!(\"{:?} not found.\", p));\n }\n }\n\n pub fn add(&mut self, p: T) {\n let index = self.uf.add();\n self.map.insert(p, index);\n }\n\n fn _find_by_index(&self, index: usize) -> Option<&T> {\n for (k, v) in self.map.iter() {\n if *v == index {\n return Some(k);\n }\n }\n None\n }\n}\n\n// #endregion\n";