#define velicina 1000
#define NISTA -1
struct grana{
        int naziv;
        int firstchild;
        int nextsibling;
};
struct drvo{
        grana id[velicina+1];
        int first;
};
struct pomocna{
        int naziv;
        int x;
};
typedef drvo stablo;
typedef int cvor;

bool goodID(int id){
        if(id<=NISTA || id>velicina) return false;
        return true;
};
stablo *InitT(pomocna x, stablo *&T){
        T = new stablo;
        T->first = x.x;
        T->id[x.x].naziv = x.naziv;
        T->id[x.x].firstchild = NISTA;
        T->id[x.x].nextsibling = NISTA;
        return T;
};
cvor RootT(stablo *T){
        return T->first;
};
cvor FirstChildT(cvor n, stablo *T){
        if(!goodID(n) || T->id[n].firstchild<=NISTA)
                return NISTA;
        return T->id[n].firstchild;
};
cvor NextSiblingT(cvor n, stablo *T){
        if(!goodID(n) || T->id[n].nextsibling<=NISTA)
                return NISTA;
        return T->id[n].nextsibling;
};
int LabelT(cvor n, stablo *T){
        if(!goodID(n) || T->id[n].naziv<=NISTA) return NISTA;
        return T->id[n].naziv;
};
cvor trazi(cvor n, cvor trazeni, cvor roditelj, stablo *T, cvor &rezultat){
        cvor tekuci = FirstChildT(n,T);
        while(tekuci>NISTA){
                trazi(tekuci,trazeni,n,T,rezultat);
                tekuci = NextSiblingT(tekuci,T);
        }
        if(n==trazeni){
                rezultat=roditelj;
                return rezultat;
        }
};
cvor ParentT(cvor n, stablo *T){
        cvor roditelj=NISTA,korijen=RootT(T);
        if(goodID(n) && korijen!=n){
                trazi(korijen,n,NISTA,T,roditelj);
                return roditelj;
        }
        return NISTA;
};
void CreateT(pomocna x, cvor n, stablo *T){
        if(!goodID(n) || !goodID(x.x)) return;
        if(FirstChildT(n,T)<=NISTA) T->id[n].firstchild = x.x;
        else{
                cvor zadnji = FirstChildT(n,T);
                while(NextSiblingT(zadnji,T)>NISTA)
                        zadnji = NextSiblingT(zadnji,T);
                T->id[zadnji].nextsibling = x.x;
        }
        T->id[x.x].naziv = x.naziv;
        T->id[x.x].firstchild = NISTA;
        T->id[x.x].nextsibling = NISTA;
};
void ChangeLabelT(pomocna x, cvor n, stablo *T){
        if(!goodID(n)) return;
        T->id[n].naziv = x.naziv;
};
void DeleteT(cvor n, stablo *T){
  if(!goodID(n)) return;
  static bool obrisan = false;
  if(!obrisan) {
    cvor roditelj = ParentT(n, T);
    if(n!=RootT(T) && roditelj!=NISTA)
      if(FirstChildT(roditelj,T)==n)
        if(NextSiblingT(roditelj,T)==NISTA)
          T->id[roditelj].firstchild=NISTA;
        else T->id[roditelj].firstchild=NextSiblingT(n,T);
      else{
        cvor zadnji = FirstChildT(roditelj,T);
        while(NextSiblingT(zadnji,T)!=n)
          zadnji = NextSiblingT(zadnji,T);
        T->id[zadnji].nextsibling = NextSiblingT(n,T);
      }
    obrisan = true;
  }
  if(FirstChildT(n,T)!=NISTA){
    DeleteT(FirstChildT(n,T),T);
    cvor pom, zadnji = FirstChildT(n,T);
    while(NextSiblingT(zadnji,T)!=NISTA){
      DeleteT(NextSiblingT(zadnji,T),T);
      pom=zadnji;
      zadnji = NextSiblingT(zadnji,T);
      T->id[pom].nextsibling = NISTA;
    }
    T->id[n].firstchild = NISTA;
  }
  obrisan = false;
};