#include <stdio.h>
#include <list>
#include <algorithm>
#include <iostream>
#include <fstream>
typedef struct node{ //노드클래스선언
node *child1;
node *child2;
int val;
bool e;
bool root;
int Pint;
int rank;
}node;
typedef struct _tagPoint{ //실행타입 매개면수 저장 구조체
int x;
int y;
}POINT;
void set_rank(node*);
node* set_e(node*);
bool cmp(node a, node b){
if(a.e > b.e)
return true;
else
return false;
}
void create_temp_rank(node* , int);
using namespace std;
FILE* file=fopen("a.txt","r");
int main()
{
int a,b;
int temp; //각노드의 부모 인자 저장 변수
POINT temp2; //실행타입 매개변수 임시저장 변수
fscanf(file,"%d",&a);
fscanf(file,"%d",&b);
//scanf("%d%d",&a,&b);
list<int> intList; //부모인자 저장 링크리스트 생성
list<POINT> intList2; //실행타입 저장 링크리스트 생성
for(int i=0;i<a;i++){ //부모인자 집어넣기
fscanf(file,"%d",&temp);
//scanf("%d",&temp);
intList.push_back(temp);
}
for(int i=b;i>0;i--){ //실행타입 집어넣기
fscanf(file,"%d",&temp2.x);
fscanf(file,"%d",&temp2.y);
//scanf("%d%d",&temp2.x,&temp2.y);
intList2.push_back(temp2);
}
list<node> nodeList; //노드 링크리스트 생성
node c; //노드의 val값 초기화를위한 변수선언
list<int>::iterator it=intList.begin();
for(int j=1;j<=a;j++){
if((*it)==0){
c.root=1;
c.val=j;
c.e=0;
c.child1=NULL;
c.child2=NULL;
c.Pint=(*it);
nodeList.push_back(c); //노드리스트의 val값 초기화
}
else{
c.root=0;
c.val=j;
c.e=0;
c.child1=NULL;
c.child2=NULL;
c.Pint=(*it);
nodeList.push_back(c);} //노드리스트의 val값 초기화
it++;
}
list<node>::iterator it2=nodeList.begin();
list<node>::iterator _it2=nodeList.begin();
for(it2;it2!=nodeList.end();it2++){
for(_it2=nodeList.begin();_it2!=nodeList.end();_it2++){
if((*it2).Pint==(*_it2).val){
if((*_it2).child1!=NULL){
if((*_it2).child1->val < (*it2).val){
(*_it2).child2 = (*_it2).child1;
(*_it2).child1=&(*it2);}
else
(*_it2).child1=&(*it2);
}
else
(*_it2).child1=&(*it2);
}
}
}
list<POINT>::iterator it3;
it3=intList2.begin();
it2=nodeList.begin();
list<node> temp_nodeList;
int last_rank;
for(it2=nodeList.begin();it2!=nodeList.end();it2++){ //라스트 랭크값 최기화;
if( (*it2).root==1){
(*it2).rank=0;
set_rank(&(*it2));
for(_it2=nodeList.begin();_it2!=nodeList.end();_it2++){
if((*_it2).child1!=NULL){
if( (*_it2).rank<(*_it2).child1->rank )
last_rank=(*_it2).child1->rank;
else
last_rank=(*_it2).rank;
}
}
}
}
for(it3;it3!=intList2.end();it3++){
if((*it3).x==1){ //실행타입 1일경우
for(it2=nodeList.begin();it2!=nodeList.end();it2++){ //라스트 랭크값 최기화;
if( (*it2).root==1){
(*it2).rank=0;
set_rank(&(*it2));
for(_it2=nodeList.begin();_it2!=nodeList.end();_it2++){
if((*_it2).child1!=NULL){
if( (*_it2).rank<(*_it2).child1->rank )
last_rank=(*_it2).child1->rank;
else
last_rank=(*_it2).rank;
}
}
}
}
for(_it2=nodeList.begin();_it2!=nodeList.end();_it2++){ //마지막랭크 링크리스트 값 집어넣기
if( (*_it2).rank==last_rank ){
temp_nodeList.push_back(*_it2);
}
}
temp_nodeList.sort(cmp); //링크 순위 정렬
it2=temp_nodeList.begin();
int y_value=(*it3).y;
while(y_value>0){
for(;y_value>0;){
for(_it2=nodeList.begin();_it2!=nodeList.end();_it2++){
if( it2==temp_nodeList.end() ) {break;}
if((*_it2).val==(*it2).val){
(*_it2).e=true;
y_value--;
it2++;
}
}
last_rank--;
if(y_value==0){
(it2)--;
printf("%d\n",(*it2).val);}
else
temp_nodeList.clear();
for(_it2=nodeList.begin();_it2!=nodeList.end();_it2++){ //마지막랭크 링크리스트 값 집어넣기
if( (*_it2).rank==last_rank ){
temp_nodeList.push_back(*_it2);
}
}
temp_nodeList.sort(cmp); //링크 순위 정렬
it2=temp_nodeList.begin();
}
}
}
else{
int two_y=(*it3).y;
for(it2=nodeList.begin();it2!=nodeList.end();it2++){
if(two_y == (*it2).val){
(*it2).e=false;
}
}
int temp_nub=0;
int _temp_nub=99;
for(int z=0;z<999;z++){
for(it2=nodeList.begin();it2!=nodeList.end();it2++){
if((*it2).child1!=NULL){
if((*it2).child1->e==false){
if( (*it2).e!=false){
(*it2).child1->e=true;
(*it2).e=false;
temp_nub++;
}
else
;
}
}
if( (*it2).child2!=NULL){
if( (*it2).child2->e==false){
if( (*it2).e!=false){
(*it2).child2->e=true;
(*it2).e=false;
temp_nub++;
}
else
;
}
}
}
if(temp_nub==_temp_nub)
break;
else
_temp_nub=temp_nub;
}
printf("%d\n",temp_nub);
temp_nub=0;
}
}
}
void set_rank(node* adr)
{
if((*adr).child1!=NULL)
(*adr).child1->rank=((*adr).rank)+1;
if((*adr).child2!=NULL)
(*adr).child2->rank=((*adr).rank)+1;
if((*adr).child1!=NULL)
set_rank((*adr).child1);
if((*adr).child2!=NULL)
set_rank((*adr).child2);
}
