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:
#if 0
cat <<EOF >mistaken-paste
#endif
// thx Ebi-chan!

// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("O3")

#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"
#define _USE_MATH_DEFINES

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>

#define BIG 2000000007LL
#define VERYBIG 20000000000000007LL
#define ULTRABIG 3000000000000000000LL

#define MOD 1000000007LL
#define FOD  998244353LL
#define HOD 1000000009LL
#define IOD  100000007LL
typedef uint64_t ull;
typedef  int64_t sll;

#define N_MAX 1048576

#ifdef __cplusplus
#include <queue>
#include <stack>
// #include <tuple>
#include <set>
#include <map>
#include <string>
#include <algorithm>
// #include <functional>
// #include <array>

using std::queue;
using std::priority_queue;
using std::stack;
// using std::tuple;
using std::set;
using std::map;
using std::vector;
using std::greater;
using std::pair;
using std::string;
// using std::get;
// using std::function;
// using std::array;

template <typename T, typename U>
pair<T, U> operator+(pair<T, U> l, pair<T, U> r) {
	return pair<T, U>(l.first + r.first, l.second + r.second);
}

#endif

#ifndef M_PI
#define M_PI 3.14159265358979323846264338327950
#endif

typedef struct {
	sll a;
	sll b;
} hwll;

typedef struct {
	sll a;
	sll b;
	sll c;
} hwllc;

typedef struct {
	hwll a;
	hwll b;
} linell;

typedef struct {
	double a;
	double b;
} hwreal;

sll n, m;
sll h, w;
sll k;
sll q;
sll va, vb, vc, vd, ve, vf;
ull ua, ub, uc, ud, ue, uf;
long double vra, vrb, vrc;
double vda, vdb, vdc;
char ch, dh;

ull umin (ull x, ull y) {
	return (x < y) ? x : y;
}

ull umax (ull x, ull y) {
	return (x > y) ? x : y;
}

sll smin (sll x, sll y) {
	return (x < y) ? x : y;
}

sll smax (sll x, sll y) {
	return (x > y) ? x : y;
}

double dmin (double x, double y) {
	return (x < y) ? x : y;
}

double dmax (double x, double y) {
	return (x > y) ? x : y;
}

ull gcd (ull x, ull y) {
	if (y == 0) {
		return x;
	} else {
		return gcd(y, x % y);
	}
}

ull bitpow (ull a, ull x, ull modulo) {
	ull result = 1;
	while (x) {
		if (x & 1) {
			result *= a;
			result %= modulo;
		}
		x /= 2;
		a = (a * a) % modulo;
	}
	return result;
}

ull divide (ull a, ull b, ull modulo) {
	return (a * bitpow(b, modulo - 2, modulo)) % modulo;
}

ull udiff (ull a, ull b) {
	if (a >= b) {
		return a - b;
	} else {
		return b - a;
	}
}

sll sdiff (sll a, sll b) {
	if (a >= b) {
		return a - b;
	} else {
		return b - a;
	}
}

int bitcount (ull n) {
	int result = 0;
	while (n) {
		if (n & 1) result++;
		n /= 2;
	}
	return result;
}

#define BEGCMP(NAME) int32_t NAME (const void *left, const void *right)
#define DEFLR(TYPE) TYPE l=*(TYPE*)left,r=*(TYPE*)right
#define CMPRET(L, R) if((L)<(R))return-1;if((L)>(R))return+1

// int32_t pullcomp (const void *left, const void *right) {
// 	ull l = *(ull*)left;
// 	ull r = *(ull*)right;
// 	if (l < r) {
// 		return -1;
// 	}
// 	if (l > r) {
// 		return +1;
// 	}
// 	return 0;
// }
BEGCMP(pullcomp){
	DEFLR(ull);
	CMPRET(l, r);
	return 0;
}
BEGCMP(prevcomp){
	DEFLR(sll);
	CMPRET(r, l);
	return 0;
}
BEGCMP(psllcomp){
	DEFLR(sll);
	CMPRET(l, r);
	return 0;
}
BEGCMP(pcharcomp){
	DEFLR(char);
	CMPRET(l, r);
	return 0;
}
BEGCMP(pdoublecomp){
	DEFLR(double);
	CMPRET(l, r);
	return 0;
}

int32_t pstrcomp (const void *left, const void *right) {
	char* l = *(char**)left;
	char* r = *(char**)right;

	return strcmp(l, r);
}

BEGCMP(phwllABcomp){
	DEFLR(hwll);
	CMPRET(l.a, r.a);
	CMPRET(l.b, r.b);
	return 0;
}
BEGCMP(phwllREVcomp){
	DEFLR(hwll);
	CMPRET(l.b, r.b);
	CMPRET(l.a, r.a);
	return 0;
}
BEGCMP(ptriplecomp){
	DEFLR(hwllc);
	CMPRET(l.a, r.a);
	CMPRET(l.b, r.b);
	CMPRET(l.c, r.c);
	return 0;
}
BEGCMP(ptripleREVcomp){
	DEFLR(hwllc);
	CMPRET(l.b, r.b);
	CMPRET(l.a, r.a);
	CMPRET(l.c, r.c);
	return 0;
}
BEGCMP(ptripleCABcomp){
	DEFLR(hwllc);
	CMPRET(l.c, r.c);
	CMPRET(l.a, r.a);
	CMPRET(l.b, r.b);
	return 0;
}
BEGCMP(phwrealcomp){
	DEFLR(hwreal);
	CMPRET(l.a, r.a);
	CMPRET(l.b, r.b);
	return 0;
}

int32_t pquadcomp (const void *left, const void *right) {
	linell l = *(linell*)left;
	linell r = *(linell*)right;

	sll ac = phwllABcomp(&(l.a), &(r.a));
	if (ac) return ac;
	sll bc = phwllABcomp(&(l.b), &(r.b));
	if (bc) return bc;

	return 0;
}
int32_t pfracomp (const void *left, const void *right) {
	hwllc l = *(hwllc*)left;
	hwllc r = *(hwllc*)right;

	CMPRET(l.a * r.b, l.b * r.a);
	return 0;
}
bool isinrange (sll left, sll x, sll right) {
	return (left <= x && x <= right);
}

bool isinrange_soft (sll left, sll x, sll right) {
	return (left <= x && x <= right) || (left >= x && x >= right);
}

void sw (sll *l, sll *r) {
	if (*l == *r) return;
	sll t = *l;
	*l = *r;
	*r = t;
}

void uw (ull *l, ull *r) {
	if (*l == *r) return;
	ull t = *l;
	*l = *r;
	*r = t;
}

ull frac[N_MAX * 3], invf[N_MAX * 3];
ull ncr (sll n, sll r, ull m) {
	if (n < 0 || r < 0 || n < r) return 0;
	return frac[n] * (invf[r] * invf[n - r] % m) % m;
}

sll a[N_MAX * 5];
// ull a[N_MAX + 5];
// sll a[3001][3001];
sll b[N_MAX * 5];
// ull b[N_MAX + 5];
// sll b[3001][3001];
sll c[N_MAX * 5];
sll d[N_MAX * 5];
sll e[N_MAX * 4];
char s[N_MAX + 1];
// char s[3010][3010];
char t[N_MAX + 1];
// char t[3010][3010];
char u[N_MAX + 1];
hwll xy[N_MAX + 5];
hwllc tup[N_MAX + 5];
// sll table[3005][3005];
sll table[1005][1005];
ull gin[N_MAX];
// here we go

double ans[N_MAX];

typedef pair<sll, sll> P;
// set<P> st;

P seg[1048576];
sll lazy[1048576];
sll base = 524288;

const P UNITY = {VERYBIG, VERYBIG};
P merge (P l, P r) {
	if (l.first < r.first) {
		return l;
	}
	if (l.first > r.first) {
		return r;
	}
	if (l.second < r.second) {
		return l;
	}
	return r;
}
// P find (sll l, sll r) {
// 	sll xl = 0, xr = 0;

// 	for ((l += base), (r += base); l < r; (l >>= 1), (r >>= 1)) {
// 		if (l % 2) xl = merge(xl, seg[l++]);
// 		if (r % 2) xr = merge(seg[--r], xr);
// 	}
// 	return merge(xl, xr);
// }
void eval (sll v) {
	seg[v].first += lazy[v];

	if (v < base) {
		lazy[v * 2] += lazy[v];
		lazy[v * 2 + 1] += lazy[v];
	}

	lazy[v] = 0;
}
P add (sll l, sll r, sll x, sll beg = 0, sll end = base, sll i = 1) {
	eval(i);
	if (end <= l || r <= beg) return UNITY;
	if (l <= beg && end <= r) {
		lazy[i] += x;
		eval(i);
		return seg[i];
	}

	sll med = (beg + end) / 2;
	P vl = add(l, r, x, beg, med, i * 2);
	P vr = add(l, r, x, med, end, i * 2 + 1);
	seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
	return merge(vl, vr);
}
void upd (sll v, sll x) {
	x -= add(v, v + 1, 0).first;
	add(v, v + 1, x);
}

sll type[N_MAX], ql[N_MAX], qr[N_MAX], qx[N_MAX];

sll cnt (ull x) {
	if (x == 0) return 0;
	return cnt(x >> 1) + (x % 2);
}

bool ischange[N_MAX];

ull parent[N_MAX], size[N_MAX];
void init (ull n) {
	for (sll i = 0; i < n; i++) {
		parent[i] = i;
		size[i] = 1;
	}
}
ull ufind (ull x) {
	if (parent[x] == x) return x;
	return parent[x] = ufind(parent[x]);
}
bool unite (ull a, ull b) {
	a = ufind(a);
	b = ufind(b);
	if (a == b) return false;

	if (size[a] < size[b]) {
		ull tmp = a;
		a = b;
		b = tmp;
	}

	size[a] += size[b];
	parent[b] = a;
	return true;
}

bool isbr[N_MAX];

sll oof[N_MAX];
sll que[N_MAX], qb, qe;

void psolve (ull beg, ull end) {
	sll i, j, ki;
	vector<ull> g[100005];

	for (i = 0; i < n; i++) ischange[i] = false;
	for (i = beg; i < end; i++) if (c[i] == 1) ischange[d[i]] = true;
	
	init(n);

	for (i = 0; i < n - 1; i++) {

		if (!ischange[a[i]] && !ischange[b[i]]) {
			if (!isbr[a[i]] && !isbr[b[i]]) {
				unite(a[i], b[i]);
			}
		}
	}

	for (i = 0; i < n - 1; i++) {
		if (!ischange[a[i]] && isbr[a[i]]) continue;
		if (!ischange[b[i]] && isbr[b[i]]) continue;

		ull v = ufind(a[i]), u = ufind(b[i]);
		if (v != u) {
			g[v].push_back(u);
			g[u].push_back(v);

			// printf("%lld-%lld\n", v, u);
		}
	}

	sll result = 0;

	for (i = beg; i < end; i++) {
		switch (c[i]) {
		case 1:
			isbr[d[i]] = !isbr[d[i]];
			break;
		case 2:
			result = 0;
			qb = qe = 0;
			oof[ufind(d[i])] = i + 1;
			que[qe++] = ufind(d[i]);

			while (qb < qe) {
				sll v = que[qb++];
				result += size[v];
				// printf("[%lld] size: %lld\n", v, size[v]);

				for (ull u : g[v]) {
					if (isbr[u]) continue;
					if (oof[u] == i + 1) continue;

					oof[u] = i + 1;
					que[qe++] = u;
				}
			}

			printf("%lld\n", result);
			break;
		}
	}
}

ull solve () {
	sll i, j, ki, li;
	// ull result = 0;
	sll result = 0;
	double dresult = 0;
	// ull maybe = 0;
	sll maybe = 0;
	// ull sum = 0;
	sll sum = 0;
	sll item;
	sll *dpcell;

	// type[0] = 1;
	// ql[0] = 0;
	// qr[0] = n;
	// qx[0] = 0;

	// for (i = 1; i <= q; i++) {
	// 	scanf("%lld%lld%lld", &type[i], &ql[i], &qr[i]);
	// 	qr[i]++;
	// 	if (type[i] == 1) scanf("%lld", &qx[i]);
	// }
	// q++;

	// for (i = base * 2 - 1; i; i--) {
	// 	if (i >= base) {
	// 		seg[i] = P(0, i - base);
	// 	} else {
	// 		seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
	// 	}
	// }

	// sll p0 = 0, p1 = n, p2 = n * 2;
	// for (i = 0; i < n; i++) {
	// 	upd(p0 + i, b[i] - a[i]);
	// 	upd(p1 + i,        b[i]);
	// 	upd(p2 + i,     VERYBIG);
	// }

	// P val;
	// for (i = 0; i < q; i++) {
	// 	switch (type[i]) {
	// 	case 1:
	// 		add(p0 + ql[i], p0 + qr[i], qx[i]);
	// 		add(p2 + ql[i], p2 + qr[i], qx[i]);
	// 		while (true) {
	// 			val = add(p0 + ql[i], p0 + qr[i], 0);
	// 			if (val.first < 0) {
	// 				sll v = val.second;

	// 				upd(p0 + v, VERYBIG);
	// 				upd(p1 + v, VERYBIG);
	// 				add(p2 + v, p2 + v + 1, -VERYBIG);
	// 			}
	// 		}
	// 		break;
	// 	case 2:
	// 		sll v1 = add(p1 + ql[i], p1 + qr[i], 0).first;
	// 		sll v2 = add(p2 + ql[i], p2 + qr[i], 0).first;

	// 		result = smin(v1, v2);
	// 		printf("%lld\n", result);
	// 		break;
	// 	}
	// }

	const ull B = 300;

	sll beg, end;
	beg = 0;
	while (beg < q) {
		end = smin(beg + B, q);

		psolve(beg, end);


		beg = end;
	}

	// printf("%lld\n", result);
	// printf("%.15f\n", dresult);
	// puts(s);

	return 0;

	success:
	// puts("YES");
	puts("Yes");
	// printf("%llu\n", result);
	// puts("0");
	// puts("First");
	return 0;

	fail:
	// puts("NO");
	puts("No");
	// puts("0");
	// puts("-1");
	// puts("-1 -1 -1");
	// puts("Second");
	return 1;
}

int32_t main (int argc, char *argv[]) {
	int32_t i, j;

	n = 3;
	m = 0;

	// scanf("%llu", &m);
	// scanf("%llu%llu", &h, &w);
	scanf("%lld", &n, &m);
	// scanf("%lld", &k, &n, &m);
	// scanf("%llu%llu", &h, &w);
	scanf("%llu", &q);
	// scanf("%lld%lld", &va, &vb, &vc, &vd);
	// va--;
	// vb--;
	// scanf("%llu%llu%llu%llu", &ua, &ub, &uc, &ud, &ue);
	// scanf("%s", s);
	// scanf("%s", t);
	// scanf("%s", u);
	// scanf("%lld", &k);
	// scanf("%lld", &m);
	// for (i = 0; i < n; i++) {
	// 	// scanf("%lld", &a[i]);
	// 	scanf("%lld", &d[i]);
	// }
	// scanf(" %c", &ch);
	// scanf("%llu", &q);
	for (i = 0; i < n - 1; i++) {
		// scanf("%lld%lld", &xy[i].a, &xy[i].b);
		// scanf("%lld%lld%lld", &tup[i].a, &tup[i].b, &tup[i].c);
		// scanf("%lld", &c[i]);

		scanf("%lld", &a[i]);
		scanf("%lld", &b[i]);
		// scanf("%lld", &c[i]);
		// scanf("%lld", &d[i]);
		a[i]--;
		b[i]--;
		// c[i]--;
		// d[i]--;
		// xy[i].a--;
		// xy[i].b--;
		// tup[i].a--;
		// tup[i].b--;
	}
	// scanf("%lld%lld", &va, &vb);
	// scanf("%llu", &m);
	// scanf("%llu", &q);
	// scanf("%s", s);
	for (i = 0; i < q; i++) {
		// scanf("%lld%lld", &xy[i].a, &xy[i].b);
		// xy[i].a--;
		// xy[i].b--;
		// scanf("%lld", &a[i], &b[i]);
		// scanf("%lld", &b[i]);
		// a[i]--;
		// b[i]--;
		scanf("%lld", &c[i]);
		scanf("%lld", &d[i]);
		// scanf("%lld", &e[i]);
		// c[i]--;
		d[i]--;
	}

	// for (i = 0; i < q; i++) {
	// 	// scanf("%lld%lld", &xy[i].a, &xy[i].b);
	// 	scanf("%lld", &c[i]);
	// 	// xy[i].a--;
	// 	// xy[i].b--;
	// }

	// for (i = 0; i < h; i++) {
	// 	for (j = 0; j < w; j++) {
	// 		scanf("%lld", &table[i][j]);
	// 		// table[i][j]--;
	// 	}
	// }
	// for (i = 0; i < h; i++) {
	// 	scanf("%s", s[i]);
	// }
	// for (i = 0; i < n; i++) {
	// 	scanf("%s", t[i]);
	// }
	// scanf("%llu", &q);

	solve();

	return 0;
}