r['~~'],c['~~'];i,j,a,b,n,x;t(k){x=r[k]!=k?r[k]=t(r[k]):k;}main(x){for(;i++<1e4?c[i]=1,r[i]=i:~scanf("%d%d",&a,&b)?a=t(a),b=t(b),--x?a-b?c[a]<c[b]||c[a]==c[b]&&a>b?a^=b^=a^=b:0,r[b]=a,c[a]+=c[b]:1:(n=a):j++<n&&printf("%d\n",t(j)););}