Problem: Bichrome Tree Connectivity

Given a tree.

Initially, all vertices are white.

Inverting the color of the white vertices makes it black, and inverting the color of the black vertices makes it white.

Handle two types of queries.

The first type of query inverts the color of vertex v.

The second type of query answers the number of vertices that can be reached from the white vertices v using only the white vertices and the edges connecting them.

input


N Q
a_1 b_1
a_2 b_2
::
a_ {n-1} b_ {n-1}
t_1 v_1
t_2 v_2
::
t_q v_q


When t_i is 1, it means that it is the first type of query, and when it is 2, it means that it is the second type of query.

output


ans_1
ans_2
::
ans_k


Output the answers to the second type of query in order.

Constraint

* 1 \ leq N, Q \ leq 10 ^ 5
* 1 \ leq a_i, b_i \ leq N
* 1 \ leq t_i \ leq 2
* 1 \ leq v_i \ leq N
* The graph given is a tree.
* When t_i = 2, the vertex v_i is always white.



Input example


10 3
1 2
twenty five
2 6
14
13
3 7
3 8
3 9
9 10
13
twenty one
2 8


Output example


Five
1






Example

Input

10 3
1 2
2 5
2 6
1 4
1 3
3 7
3 8
3 9
9 10
1 3
2 1
2 8


Output

5
1

Solution (in CPP):

Solution:
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3120"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename Node, size_t LIM>
struct LinkCutTreeBase{
  static array<Node, LIM> pool;
  size_t ptr;

  LinkCutTreeBase():ptr(0){}

  inline Node* create(){
    return &pool[ptr++];
  }

  inline Node* create(Node v){
    return &(pool[ptr++]=v);
  }

  inline size_t idx(Node *t){
    return t-&pool[0];
  }

  Node* operator[](size_t k){
    return &(pool[k]);
  }

  virtual void toggle(Node *t) = 0;
  virtual void eval(Node *t) = 0;
  virtual void pushup(Node *t) = 0;

  void rotR(Node *t){
    Node *x=t->p,*y=x->p;
    if((x->l=t->r)) t->r->p=x;
    t->r=x;x->p=t;
    pushup(x);pushup(t);
    if((t->p=y)){
      if(y->l==x) y->l=t;
      if(y->r==x) y->r=t;
      pushup(y);
    }
  }

  void rotL(Node *t){
    Node *x=t->p,*y=x->p;
    if((x->r=t->l)) t->l->p=x;
    t->l=x;x->p=t;
    pushup(x);pushup(t);
    if((t->p=y)){
      if(y->l==x) y->l=t;
      if(y->r==x) y->r=t;
      pushup(y);
    }
  }

  bool is_root(Node *t){
    return !t->p||(t->p->l!=t&&t->p->r!=t);
  }

  void splay(Node *t){
    eval(t);
    while(!is_root(t)){
      Node *q=t->p;
      if(is_root(q)){
        eval(q);eval(t);
        if(q->l==t) rotR(t);
        else rotL(t);
      }else{
        auto *r=q->p;
        eval(r);eval(q);eval(t);
        if(r->l==q){
          if(q->l==t) rotR(q),rotR(t);
          else rotL(t),rotR(t);
        }else{
          if(q->r==t) rotL(q),rotL(t);
          else rotR(t),rotL(t);
        }
      }
    }
  }

  virtual Node* expose(Node *t){
    Node *rp=nullptr;
    for(Node *c=t;c;c=c->p){
      splay(c);
      c->r=rp;
      pushup(c);
      rp=c;
    }
    splay(t);
    return rp;
  }

  void link(Node *par,Node *c){
    expose(c);
    expose(par);
    c->p=par;
    par->r=c;
    pushup(par);
  }

  void cut(Node *c){
    expose(c);
    Node *par=c->l;
    c->l=nullptr;
    pushup(c);
    par->p=nullptr;
  }

  void evert(Node *t){
    expose(t);
    toggle(t);
    eval(t);
  }

  Node *parent(Node *t){
    expose(t);
    t=t->l;
    while(t&&t->r){
      eval(t);
      t=t->r;
    }
    if(t) splay(t);
    return t;
  }

  Node *root(Node *t){
    expose(t);
    while(t->l){
      eval(t);
      t=t->l;
    }
    splay(t);
    return t;
  }

  bool is_connected(Node *a,Node *b){
    return root(a)==root(b);
  }

  Node *lca(Node *a,Node *b){
    expose(a);
    return expose(b);
  }
};
template<typename Node, size_t LIM>
array<Node, LIM> LinkCutTreeBase<Node, LIM>::pool;
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "base.cpp"
#undef call_from_test

#endif
//BEGIN CUT HERE
template<typename Ap>
struct NodeBase{
  using A = Ap;
  NodeBase *l,*r,*p;
  bool rev;
  A val,dat,sum;
  NodeBase(){}
  NodeBase(A val,A dat,A sum):
    rev(0),val(val),dat(dat),sum(sum){
    l=r=p=nullptr;}
};

template<typename Np, size_t LIM>
struct SubTree : LinkCutTreeBase<Np, LIM>{
  using super = LinkCutTreeBase<Np, LIM>;
  using Node = Np;
  using A = typename Node::A;

  SubTree():super(){}

  Node* create(A val){
    return super::create(Node(val,A(),val));
  }

  inline void toggle(Node *t){
    swap(t->l,t->r);
    t->rev^=1;
  }

  inline void eval(Node *t){
    if(t->rev){
      if(t->l) toggle(t->l);
      if(t->r) toggle(t->r);
      t->rev=false;
    }
  }

  inline A resolve(Node *t){
    return t?t->sum:A();
  }

  inline void pushup(Node *t){
    if(t==nullptr) return;
    t->sum=t->val+t->dat;
    t->sum+=resolve(t->l);
    t->sum+=resolve(t->r);
  }

  using super::splay;

  Node* expose(Node *t){
    Node *rp=nullptr;
    for(Node *c=t;c;c=c->p){
      splay(c);
      c->dat+=resolve(c->r);
      c->r=rp;
      c->dat-=resolve(c->r);
      pushup(c);
      rp=c;
    }
    splay(t);
    return rp;
  }

  A query(Node *t){
    expose(t);
    return t->sum;
  }

  void set_val(Node *t,A a){
    expose(t);
    t->val=a;
    pushup(t);
  }
};
//END CUT HERE
#ifndef call_from_test

#define call_from_test
#include "../tools/fastio.cpp"
#undef call_from_test

//INSERT ABOVE HERE

// sum of square
signed CFR564_E(){
  int n,m;
  cin>>n>>m;
  vector<vector<int>> modv(n),modt(n);
  vector<int> cs(n);

  for(int i=0;i<n;i++){
    cin>>cs[i];
    cs[i]--;
    modv[cs[i]].emplace_back(i);
    modt[cs[i]].emplace_back(0);
  }

  vector<vector<int> > G(n+1);
  for(int i=1;i<n;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  G[n].emplace_back(0);

  for(int i=1;i<=m;i++){
    int v,x;
    cin>>v>>x;
    v--;x--;
    modv[cs[v]].emplace_back(v);
    modt[cs[v]].emplace_back(i);
    cs[v]=x;
    modv[cs[v]].emplace_back(v);
    modt[cs[v]].emplace_back(i);
  }

  using ll = long long;
  struct A{
    ll sz1,sz2;
    A():sz1(0),sz2(){}
    A(ll sz1,ll sz2):sz1(sz1),sz2(sz2){}
    A operator+(const A &a)const{
      return A(sz1+a.sz1,sz2+a.sz2);
    };
    A& operator+=(const A &a){
      sz1+=a.sz1;
      sz2+=a.sz1*a.sz1;
      return (*this);
    }
    A& operator-=(const A &a){
      sz1-=a.sz1;
      sz2-=a.sz1*a.sz1;
      return (*this);
    }
  };

  using Node = NodeBase<A>;
  constexpr size_t LIM = 1e6;
  using LCT = SubTree<Node, LIM>;
  LCT lct;

  for(int i=0;i<n+1;i++) lct.create(A(1,0));

  vector<int> par(n+1,0);
  {
    using P = pair<int, int>;
    queue<P> q;
    q.emplace(n,-1);
    while(!q.empty()){
      int v,p;
      tie(v,p)=q.front();q.pop();
      par[v]=p;
      if(~p) lct.link(lct[p],lct[v]);
      for(int u:G[v])
        if(u!=p) q.emplace(u,v);
    }
  }

  vector<ll> delta(m+1,0);
  vector<int> color(n+1,0);

  for(int c=0;c<n;c++){
    ll lst=(ll)n*n,cur=(ll)n*n;
    delta[0]+=lst;

    if(modv[c].empty()) continue;
    for(int i=0;i<(int)modv[c].size();i++){
      int v=modv[c][i];
      color[v]^=1;
      if(color[v]){
        cur-=lct.query(lct.root(lct[v])).sz2;
        lct.cut(lct[v]);
        cur+=lct.query(lct.root(lct[par[v]])).sz2;
        cur+=lct.query(lct[v]).sz2;
      }else{
        cur-=lct.query(lct.root(lct[par[v]])).sz2;
        cur-=lct.query(lct[v]).sz2;
        lct.link(lct[par[v]],lct[v]);
        cur+=lct.query(lct.root(lct[v])).sz2;
      }
      if(i+1==(int)modv[c].size()||modt[c][i]!=modt[c][i+1]){
        delta[modt[c][i]]+=cur-lst;
        lst=cur;
      }
    }

    for(int i=0;i<(int)modv[c].size();i++){
      int v=modv[c][i];
      if(!color[v]) continue;
      color[v]^=1;
      lct.link(lct[par[v]],lct[v]);
    }
  }

  ll ans=(ll)n*n*n;
  for(int i=0;i<=m;i++){
    ans-=delta[i];
    cout<<ans<<"\n";
  }
  cout<<flush;
  return 0;
}
/*
  verified on 2019/12/27
  https://codeforces.com/contest/1172/problem/E
*/

// test root
signed NIKKEI2019_QUAL_E(){
  int n,m;
  cin>>n>>m;
  vector<int> xs(n);
  for(int i=0;i<n;i++) cin>>xs[i];
  using T = tuple<int, int, int>;
  vector<T> vt;
  for(int i=0;i<m;i++){
    int a,b,y;
    cin>>a>>b>>y;
    a--;b--;
    vt.emplace_back(y,a,b);
  }
  sort(vt.begin(),vt.end());

  using ll = long long;
  using Node = NodeBase<ll>;
  constexpr size_t LIM = 1e6;
  using LCT = SubTree<Node, LIM>;
  LCT lct;

  for(int i=0;i<n;i++) lct.create(xs[i]);

  using P = pair<int, int>;
  set<P> es;
  for(auto t:vt){
    int a,b;
    tie(ignore,a,b)=t;
    if(lct.is_connected(lct[a],lct[b])) continue;
    lct.evert(lct[b]);
    lct.link(lct[a],lct[b]);
    es.emplace(a,b);
  }

  int ans=0;
  reverse(vt.begin(),vt.end());
  for(auto t:vt){
    int y,a,b;
    tie(y,a,b)=t;
    auto rt=lct.root(lct[a]);
    ll sum=lct.query(rt);
    if(sum>=y) continue;
    ans++;
    if(es.count(P(a,b))){
      lct.evert(lct[a]);
      lct.cut(lct[b]);
    }
  }

  cout<<ans<<endl;
  return 0;
}
/*
  verified on 2019/12/27
  https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_e
*/

signed main(){
  //CFR564_E();
  //NIKKEI2019_QUAL_E();
  return 0;
}
#endif

#undef call_from_test

signed main(){
  using Node = NodeBase<int>;
  constexpr size_t LIM = 1e5+100;
  using LCT = SubTree<Node, LIM>;
  LCT lct;

  int n,q;
  cin>>n>>q;

  for(int i=0;i<=n;i++) lct.create(1);
  for(int i=1;i<n;i++){
    int a,b;
    cin>>a>>b;
    lct.evert(lct[b]);
    lct.link(lct[a],lct[b]);
  }
  lct.evert(lct[1]);
  lct.link(lct[0],lct[1]);

  vector<int> par(n+1);
  for(int i=1;i<=n;i++) par[i]=lct.idx(lct.parent(lct[i]));

  for(int i=0;i<q;i++){
    int t,v;
    cin>>t>>v;
    if(t==1){
      if(lct.root(lct[v])==lct[v]){
        lct.link(lct[par[v]],lct[v]);
      }else{
        lct.cut(lct[v]);
      }
    }
    if(t==2){
      auto r=lct.root(lct[v]);
      lct.evert(lct[v]);
      auto u=lct.parent(r);
      lct.evert(r);
      lct.cut(u);
      cout<<lct.query(u)<<"\n";
      lct.link(r,u);
    }
  }
  cout<<flush;
  return 0;
}