RollBack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define mp make_pair
#define pb push_back

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")

constexpr long long INF = (long long)2e9;
constexpr int N = (int)5e5 + 111;
constexpr int md = (int)1e9 + 7;
constexpr int mdPower = (int)1e9+7 - 1;
constexpr int P = (int)998244343;
constexpr double PI = acos(-1);

//typedef __int128 _uint;
typedef long long ll;

mt19937_64 rnd(time(nullptr));

void add(int& a,int b){
    a += b; if(a >= md) a -= md;
}
void sub(int& a,int b){
    a -= b; while(a < 0) a += md;
}

int bpow(int a,int b){
    if(b == 0)
        return 1;
    if(b % 2 == 0){
        int t = bpow(a,b>>1);
        return 1ll*t*t%md;
    }
    return 1ll * a*bpow(a,b-1) % md;
}

int inv(int a){
    return bpow(a,md-2);
}

//int fac[N],invfac[N];
//
//void init(){
//    fac[0] = 1;
//    for(int i = 1; i < N; i++){
//        fac[i] = (fac[i-1] * i) % md;
//    }
//    invfac[N-1] = inv(fac[N-1]);
//    for(int i = N-2; i >= 0; i--){
//        invfac[i] = (invfac[i+1] * (i+1))%md;
//    }
//    return;
//}
//
//int C(int n,int k){
//    if(k > n)
//        return 0;
//    return fac[n] * invfac[k] % md * invfac[n-k] % md;
//}
//
//int A(int n,int k){
//    if(k > n)
//        return 0;
//    return fac[n] * invfac[n-k] % md;
//}
int parent[N];
int sz[N];
vector<pair<pair<int,int>,pair<int,int>>> history;
int deep[N];

int get(int x){
    if(parent[x] == x)
        return x;
    return get(parent[x]);
}

void union_sets(int a,int b){
    a = get(a), b = get(b);
    if(a == b)
        return;
    if(deep[a] > deep[b])
        swap(a,b);
    history.pb(mp(mp(a,parent[a]),mp(sz[b],deep[b])));
    deep[b] = max(deep[b],deep[a]+1);
    parent[a] = b;
    sz[b] += sz[a];
    return;
}

void roll_back(int S){
    assert(!history.empty());
    while(history.size() > S){
        int a = history.back().first.first, b = history.back().first.second, prevSZ = history.back().second.first;
        int d = history.back().second.second;
        history.pop_back();
        sz[parent[a]] = prevSZ;
        deep[parent[a]] = d;
        parent[a] = b;
    }
    return;
}

vector<pair<int,int>> t[4*N];

void upd(int v,int l,int r,int tl,int tr,pair<int,int>& x){
    if(l > r || tl > tr)
        return;
    if(l == tl && r == tr){
        t[v].pb(x);
        return;
    }
    int m = (l+r)>>1;
    upd(v<<1,l,m,tl,min(tr,m),x);
    upd(v<<1|1,m+1,r,max(tl,m+1),tr,x);
    return;
}
int getSz(int a){
    a = get(a);
    return sz[a];
}

vector<pair<int,int>> edges;
int cnt[4*N];
int Query[4*N];
int ans[N];
map<pair<int,int>,int> pr;
map<pair<int,int>,int> cur;

void updEdge(int v,int l,int r,int tl,int tr,pair<int,int>& x){
    if(l > r || tl > tr)
        return;
    if(l == tl && r == tr){
        t[v].pb(x);
        return;
    }
    int m = (l+r)>>1;
    updEdge(v<<1,l,m,tl,min(tr,m),x);
    updEdge(v<<1|1,m+1,r,max(tl,m+1),tr,x);
    return;
}

void updQuery(int v,int l,int r,int pos,int x){
    if(l > r)
        return;
    if(l == r){
        Query[v] = x;
        cnt[v] = 1;
        return;
    }
    int m = (l+r)>>1;
    if(pos <= m)
        updQuery(v<<1,l,m,pos,x);
    else
        updQuery(v<<1|1,m+1,r,pos,x);
    cnt[v] = cnt[v<<1] + cnt[v<<1|1];
    return;
}

int CC = 0;

void go(int v,int l,int r){
    if(l > r)
        return;
    int sz = history.size();
//    CC++;
//    if(CC % 10000 <= 5)
//        cerr << "go " << v << " " << l << " " << r << "\n";
    for(auto&[x,y] : t[v]){
        union_sets(x,y);
//        cerr << "adding " << x << " " << y << "\n";
    }
    if(l == r){
        if(Query[l] != 0){
//            cerr << "have " << l << "\n";
            int x = Query[l];
            ans[l] = getSz(x);
//            cerr << "x = " << x << "\n";
//            cerr << "sz = " << ans[l] << "\n";
        }
    } else {
        int m = (l+r)>>1;
        go(v<<1,l,m);
        go(v<<1|1,m+1,r);
    }
    roll_back(sz);
    return;
}

int p[N];
vector<int> g[N];
vector<int> gr[N];

void dfs(int v){
    for(auto& to : g[v]){
        if(to == p[v])
            continue;
        p[to] = v;
        dfs(to);
    }
    return;
}

void solve(){
    int n,q;
    n = q = 100000;
//    cin >> n >> q;

    auto start_time = chrono::steady_clock::now();

    for(int i = 0; i < N; i++){
        parent[i] = i;
        sz[i] = 1;
        deep[i] = 1;
    }

    for(int i = 1; i < n; i++){
        int a,b;
//        cin >> a >> b;
        a = rnd()%i + 1;
        b = i;
        g[a].pb(b);
        g[b].pb(a);
        if(a > b)
            swap(a,b);
        edges.pb(mp(a,b));
        cur[mp(a,b)] = 1;
        pr[mp(a,b)] = 1;
    }

    dfs(1);

    for(int i = 1; i <= q; i++){
        int tp,x;
        tp = rnd()%2+1;
        if(tp == 1) x = rnd()%(n-1) + 2; else x = rnd()%n+1;
//        cin >> tp >> x;
        if(tp == 1){
            int a = p[x], b = x;
            if(a > b)
                swap(a,b);
            cur[mp(a,b)] ^= 1;
//            cerr << "edge " << a << " " << b << "\n";
            int l = pr[mp(a,b)];
            if(cur[mp(a,b)] == false){
                pair<int,int> x = mp(a,b);
                updEdge(1,1,q,l,i,x);
            } else {
                pr[mp(a,b)] = i;
            }
        } else {
//            cerr << "query " << i << "\n";
//            updQuery(1,1,q,i,x);
            Query[i] = x;
        }
    }

    for(int i = 2; i <= n; i++){
        int a = i, b = p[i];
        if(a > b)
            swap(a,b);
        if(cur[mp(a,b)] == 1){
            int l = pr[mp(a,b)];
            pair<int,int> x = mp(a,b);
            updEdge(1,1,q,l,q,x);
        }
    }

    auto cur_time = chrono::steady_clock::now();
    int dur = chrono::duration_cast<chrono::milliseconds>(cur_time-start_time).count();
    cerr << "dur = " << dur << "\n";

    for(int i = 1; i <= q; i++) ans[i] = -1;

    go(1,1,q);

    for(int i = 1; i <= q; i++){
        if(ans[i] != -1)
            cout << ans[i] << "\n";
    }

    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tests = 1;
//    cin >> tests;
    for(int test = 1; test <= tests; test++){
//        cerr << "test = " << test << "\n";
        solve();
    }
    return 0;
}
/**


**/