i,j,a,p[2][1<<17],*q=p;main(n,k,x,y,z){for(scanf("%d%d%d ",&n,&k,&x);n/++i?q[i]=p[1][i]=i:k?--k,--x?scanf("%d%d ",&y,&z),n=x>0,p[n][y]^=p[n][z]^=p[n][y]^=p[n][z]:gets(&y):~scanf("%d",&x)?x-p[1][y=q[++j]]?a?n=y:(a=y):1:0;);a=!printf("%d %d",a<n?a:n,a<n?n:a);}