#include using namespace std; constexpr int MAXN=1e5+10, inf=2e9; #define ch(p) tr[p].ch #define fa(p) tr[p].fa #define ls(p) ch(p)[0] #define rs(p) ch(p)[1] #define dis2(p) tr[p].dis2 #define vdis(p) (dis2(p).empty()?inf:*dis2(p).begin()) #define val(p) tr[p].val #define lmn(p) tr[p].lmn #define rmn(p) tr[p].rmn #define isroot(p) (ls(fa(p))!=p&&rs(fa(p))!=p) #define gc(p) (p==rs(fa(p))) #define siz(p) tr[p].siz struct node { int ch[2], fa, val; int lmn, rmn, siz; multiset dis2; } tr[MAXN<<2]; void pushup(int x) { siz(x)=1+siz(ls(x))+siz(rs(x)); lmn(x)=min(lmn(ls(x)),siz(ls(x))+min(val(x)*inf,min(vdis(x),lmn(rs(x))+1))); rmn(x)=min(rmn(rs(x)),siz(rs(x))+min(val(x)*inf,min(vdis(x),rmn(ls(x))+1))); } void rotate(int x) { int y=fa(x), z=fa(y), k=gc(x); fa(x)=z; if(!isroot(y)) ch(z)[gc(y)]=x; ch(y)[k]=ch(x)[k^1]; fa(ch(x)[k^1])=y; ch(x)[k^1]=y; fa(y)=x; pushup(y); pushup(x); } void splay(int x) { for (int y; y=fa(x),!isroot(x); rotate(x)) if (!isroot(y)) rotate(gc(x)==gc(y)?y:x); } void access(int x) { int y=0; while (x) { splay(x); if (rs(x)) dis2(x).insert(lmn(rs(x))+1); if (y) dis2(x).erase(dis2(x).find(lmn(y)+1)); rs(x)=y; pushup(x); y=x; x=fa(x); } } vector g[MAXN]; void dfs(int u, int fa) { fa(u)=fa; for (auto v: g[u]) if (v!=fa) { dfs(v,u); dis2(u).insert(lmn(v)+1); } pushup(u); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin>>n; lmn(0)=rmn(0)=inf; for (int i=1; i<=n; ++i) val(i)=1; for (int i=1,u,v; i>u>>v, g[u].push_back(v), g[v].push_back(u); dfs(1,0); int m, op, u; cin>>m; while (m--) { cin>>op>>u; access(u); splay(u); if (op==1) { val(u)^=1; splay(u); } else { int res=rmn(u)