import java.util.Arrays; import java.util.Scanner; import java.io.*; class Main { public static void main(String[] args) { new Main().run(); } class DJSet{ int n; int[] upper; public DJSet(int n){ this.n=n; upper=new int[n]; Arrays.fill(upper,-1); } boolean equiv(int a,int b){ return root(a)==root(b); } int root(int x){ return upper[x]<0?x:(upper[x]=root(upper[x])); } void setUnion(int a,int b){ a=root(a); b=root(b); if(a==b)return; if(upper[a]