#include using namespace std; #define REP(i,a,b) for(i=a;i'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);} template void reader(T *x, S *y){reader(x);reader(y);} template void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);} void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);} template void writerLn(T x){writer(x,'\n');} char memarr[17000000]; void *mem = memarr; struct unionFind{ int *d, N, M; inline void malloc(int n){d=(int*)std::malloc(n*sizeof(int));M=n;} inline void *malloc(int n, void *mem){d=(int*)mem;M=n;return d+n;} inline void init(int n){int i;N=n;rep(i,n)d[i]=-1;} inline void init(void){init(M);} inline int get(int a){int t=a,k;while(d[t]>=0)t=d[t];while(d[a]>=0)k=d[a],d[a]=t,a=k;return a;} inline int connect(int a, int b){if(d[a]>=0)a=get(a);if(d[b]>=0)b=get(b);if(a==b)return 0;if(d[a]