#include #include #include #include #include using namespace std; typedef int number; struct monkey { monkey() : parent(0) ,r(0) ,left(0) ,right(0) { } number right; number left; number id; monkey* parent; set monkeys; list un; number r; }; struct event { number monkey; number second; }; monkey * find(monkey * a) { if(a==a->parent)return a; else { monkey * tmp=find(a->parent); a->parent=tmp; return tmp; } } void gunion(monkey * a,monkey * b) { monkey * ga,* gb; ga=find(a); gb=find(b); list::iterator it; if(gb!=ga) { if(ga->r == gb->r) { gb->un.splice(gb->un.begin(),ga->un); ga->parent=gb; gb->r++; } else if( ga->r < gb->r) { gb->un.splice(gb->un.begin(),ga->un); ga->parent=gb; } else if(ga->r > gb->r) { ga->un.splice(ga->un.begin(),gb->un); gb->parent=ga; } } } vector events; int main() { //fstream in; //in.open("mal1.in"); number * answer=new number[200001]; monkey * G=new monkey[200001]; for(int i=0;i<=200000;i++) { answer[i]=0; G[i].parent=&G[i]; G[i].id=i; G[i].un.push_back(i); } int N,M; scanf("%d %d",&N,&M); for(int i=1;i<=N;i++) { int l,r; scanf("%d %d",&l,&r); if(l!=-1) { G[i].monkeys.insert(l); G[i].left=l; } if(r!=-1) { G[i].monkeys.insert(r); G[i].right=r; } } for(int i=1;i<=M;i++) { int who,hand; scanf("%d %d",&who,&hand); if(hand==1) { G[who].monkeys.erase(G[who].left); } if(hand==2) { G[who].monkeys.erase(G[who].right); } event tmp; tmp.monkey=who; tmp.second=hand; events.push_back(tmp); } bool * visited=new bool[N+1]; for(int i=0;i<=N;i++)visited[i]=0; list bfs; bfs.push_back(1); monkey* start = &G[1]; for(int i=1;i<=N;i++) { set::iterator neigh; neigh=G[i].monkeys.begin(); while(neigh!=G[i].monkeys.end() ) { gunion(&G[*neigh],&G[i]); neigh++; } } list::iterator it; it=G[find(&G[1])->id].un.begin(); while(it!=G[find(&G[1])->id].un.end()) { answer[*it]=-1; it++; } G[G[1].parent->id].un.clear(); for(int i=M-1;i>=0;i--) { event tmp=events[i]; if(tmp.second==1) { if(find(&G[tmp.monkey]) != find(&G[G[tmp.monkey].left])) { gunion(&G[tmp.monkey],&G[G[tmp.monkey].left]); } } if(tmp.second==2) { if(find(&G[tmp.monkey]) != find(&G[G[tmp.monkey].right])) { gunion(&G[tmp.monkey],&G[G[tmp.monkey].right]); } } it=G[find(&G[1])->id].un.begin(); while(it!=G[find(&G[1])->id].un.end()) { answer[*it]=i; it++; } G[G[1].parent->id].un.clear(); } for(int i=1;i<=N;i++)printf("%d\n",answer[i]); }