i,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,i=n=--x>0,x?scanf("%d%d ",&y,&z),p[n][y]^=p[n][z]^=p[n][y]^=p[n][z]:gets(&y):~scanf("%d",&x)?x-p[1][y=q[i]]?a?z=y:(a=y):1:0;);a=!printf("%d %d",a<z?a:z,a<z?z:a);}