class DSU { private int n; private int[] parentOrSize; public DSU(int n) { this.n = n; this.parentOrSize = new int[n]; java.util.Arrays.fill(parentOrSize, -1); } int merge(int a, int b) { if (!(0 <= a && a < n)) throw new IndexOutOfBoundsException("a=" + a); if (!(0 <= b && b < n)) throw new IndexOutOfBoundsException("b=" + b); int x = leader(a); int y = leader(b); if (x == y) return x; if (-parentOrSize[x] < -parentOrSize[y]) { int tmp = x; x = y; y = tmp; } parentOrSize[x] += parentOrSize[y]; parentOrSize[y] = x; return x; } boolean same(int a, int b) { if (!(0 <= a && a < n)) throw new IndexOutOfBoundsException("a=" + a); if (!(0 <= b && b < n)) throw new IndexOutOfBoundsException("b=" + b); return leader(a) == leader(b); } int leader(int a) { if (parentOrSize[a] < 0) { return a; } else { parentOrSize[a] = leader(parentOrSize[a]); return parentOrSize[a]; } } int size(int a) { if (!(0 <= a && a < n)) throw new IndexOutOfBoundsException("" + a); return -parentOrSize[leader(a)]; } java.util.ArrayList> groups() { int[] leaderBuf = new int[n]; int[] groupSize = new int[n]; for (int i = 0; i < n; i++) { leaderBuf[i] = leader(i); groupSize[leaderBuf[i]]++; } java.util.ArrayList> result = new java.util.ArrayList<>(n); for (int i = 0; i < n; i++) { result.add(new java.util.ArrayList<>(groupSize[i])); } for (int i = 0; i < n; i++) { result.get(leaderBuf[i]).add(i); } result.removeIf(java.util.ArrayList::isEmpty); return result; } }