Chef has a tree consisting of N nodes, rooted at node 1. Every node of this tree can be assigned a binary value (0 or 1). Initially, every node is assigned 0.

We define AND-value of a set of nodes as the [bitwise AND] of all the values of the nodes in it.  
An edge in the tree is called good, if after removing this edge, the two trees obtained have the same AND-value.

You have to process Q queries. Each query is one of the following types :
1 u : If node u is a leaf, change its value to 1, else, change its value to the AND-value of its *descendants*.
2 : Find the total number of *good* edges in the tree.

Note: *Descendants* of some node X, are all the nodes in its [subtree],subset%20of%20the%20larger%20tree.) except X.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N — the number of nodes in the tree.
- The next N-1 lines describe the edges. The i^{th} line contains two space-separated integers u_{i} and v_{i}, denoting an edge between u_{i} and v_{i}.
- The next line contains a single integer Q — the number of queries.
- Then, Q lines follow. Each of these lines describes a query in the format described above.

------ Output Format ------ 

For each query of the second type, print a single line containing one integer — the number of good edges in the tree.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 3 \cdot 10^{5}$
$1 ≤ Q ≤ 3 \cdot 10^{5}$
$1 ≤ u_{i}, v_{i} ≤ N$ and $u_{i} \neq v_{i}$.
- The sum of $N$ and $Q$ over all test cases won't exceed $3 \cdot 10^{5}$.
- Atleast one query of type $2$ is present.

----- Sample Input 1 ------ 
1
5
1 2
1 3
2 4
2 5
5
1 1
1 3
2
1 5
2

----- Sample Output 1 ------ 
3
2
----- explanation 1 ------ 
Query $1$: Node $1$ is not a leaf node. Thus, we change its value to the AND-value of its *descendants*. Descendants of node $1$ are $\{2, 3, 4, 5\}$. All these nodes have value $0$. Thus, the bitwise AND of all values is also $0$. Hence, node $1$ is assigned $0$.

Query $2$: Node $3$ is assigned $1$ since it is a leaf node.

Query $3$: Edges between nodes $(1, 2), (2, 4),$ and $(2, 5)$ are good edges.
- Edge $(1, 2)$: On removing the edge the set of nodes in the two trees are $\{1, 3\}$ and $\{2, 4, 5\}$. The AND-values of the respective set of nodes is $0$ $\&$ $1 = 0$ and $0$ $\&$ $0$ $\&$ $0 = 0$, which is equal.
- Edge $(2, 4)$: On removing the edge the set of nodes in the two trees are $\{4\}$ and $\{1, 2, 3, 5\}$. The AND-values of the respective set of nodes is $0$ and $0$ $\&$ $0$ $\&$ $1$ $\&$ $0 = 0$, which is equal.
- Edge $(2, 5)$: On removing the edge the set of nodes in the two trees are $\{5\}$ and $\{1, 2, 3, 4\}$. The AND-values of the respective set of nodes is $0$ and $0$ $\&$ $0$ $\&$ $1$ $\&$ $0 = 0$, which is equal.

Query $4$: Node $5$ is assigned $1$ since it is a leaf node.

Query $5$: Edges between nodes $(1, 2)$ and $(2, 4)$ are good edges.

Source: codechef | Difficulty: HARD
Tags: Bit manipulation

Graph algorithms

Graph traversal

Greedy algorithms

Tree algorithms

Mathematics

Data structures


Solutions:
import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache
import bisect
import heapq
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, arr, func=lambda x, y: x + y, defaultvalue=0):
		self.n = len(arr)
		self.segmentTree = [0] * self.n + arr
		self.func = func
		self.defaultvalue = defaultvalue
		self.buildSegmentTree(arr)

	def buildSegmentTree(self, arr):
		for i in range(self.n - 1, 0, -1):
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		res = self.defaultvalue
		while l < r:
			if l & 1:
				res = self.func(res, self.segmentTree[l])
				l += 1
			l >>= 1
			if r & 1:
				r -= 1
				res = self.func(res, self.segmentTree[r])
			r >>= 1
		return res

	def update(self, i, value):
		i += self.n
		self.segmentTree[i] = value
		while i > 1:
			i >>= 1
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	n = int(input())
	mapp = defaultdict(set)
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		mapp[a].add(b)
		mapp[b].add(a)
	parentmapp = defaultdict(lambda : -1)
	needed = defaultdict(lambda : 0)

	def remove_parent(i, p=None):
		if p != None:
			parentmapp[i] = p
			needed[p] += 1
			mapp[i].remove(p)
		for j in mapp[i]:
			remove_parent(j, i)
	remove_parent(1)
	dp = [0] * (n + 1)
	dp[0] = -1
	ans = n - 1
	q = int(input())
	for i in range(q):
		v = list(map(int, input().split()))
		if v[0] == 1:
			zc = needed[v[1]]
			if zc == 0 and dp[v[1]] == 0:
				dp[v[1]] = 1
				if v[1] != 1:
					needed[parentmapp[v[1]]] -= 1
					ans -= 1
				else:
					ans = n - 1
		else:
			print(ans)
for t in range(int(input())):
	solve()


import sys
sys.setrecursionlimit(1000000)

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
from collections import deque, Counter
from heapq import heappush, heappop
for _ in range(int(input())):

	def solve():
		n = int(input())
		adj = [[] for _ in range(n)]
		res = n - 1
		par = [-1 for _ in range(n)]
		ch = [0 for _ in range(n)]
		for _ in range(n - 1):
			(u, v) = get_ints()
			adj[u - 1].append(v - 1)
			adj[v - 1].append(u - 1)

		def dfs(node, pa):
			for an in adj[node]:
				if an != pa:
					par[an] = node
					ch[node] += 1
					dfs(an, node)
		dfs(0, -1)
		vis = [False for _ in range(n)]
		for _ in range(int(input())):
			qu = get_list()
			if qu[0] == 1:
				if ch[qu[1] - 1] == 0:
					if vis[qu[1] - 1]:
						continue
					if qu[1] == 1:
						res = n - 1
						continue
					res -= 1
					vis[qu[1] - 1] = True
					if qu[1] != 1:
						ch[par[qu[1] - 1]] -= 1
			else:
				print(res)
	solve()


def dfs(curr, ar, ct, tree):
	count = 0
	for i in ar[curr]:
		if tree[curr] == i:
			continue
		tree[i] = curr
		count += dfs(i, ar, ct, tree)
	ct[curr] = count
	return 1
t = int(input())
for _ in range(t):
	n = int(input())
	l = [[] for _ in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		l[u].append(v)
		l[v].append(u)
	ct = [0 for _ in range(n + 1)]
	tree = [0 for _ in range(n + 1)]
	dfs(1, l, ct, tree)
	q = int(input())
	g_ct = n - 1
	one = [False] * (n + 1)
	for _ in range(q):
		ar = list(map(int, input().split()))
		if ar[0] == 1:
			curr = ar[1]
			if ct[curr] == 0 and (not one[curr]):
				ct[tree[curr]] -= 1
				g_ct -= 1
				one[curr] = True
		else:
			print(n - 1 if one[1] else g_ct)


def order(parent, children, thisdict, visited, element, par):
	if visited[element] == True:
		return
	visited[element] = True
	parent[element] = par
	if par != -1:
		children[par].append(element)
	for i in thisdict[element]:
		if visited[i] == False:
			order(parent, children, thisdict, visited, i, element)
for i in range(int(input())):
	N = int(input())
	thisdict = {}
	value = [0 for _ in range(N)]
	parent = [-1 for i in range(N)]
	children = [[] for i in range(N)]
	visited = [False for i in range(N)]
	for i in range(N - 1):
		(u, v) = input().split()
		u = int(u) - 1
		v = int(v) - 1
		if u in thisdict:
			thisdict[u].append(v)
		else:
			thisdict[u] = [v]
		if v in thisdict:
			thisdict[v].append(u)
		else:
			thisdict[v] = [u]
	order(parent, children, thisdict, visited, 0, -1)
	Q = int(input())
	ones = 0
	for i in range(Q):
		x = input().split()
		type = int(x[0])
		if type == 1:
			index = int(x[1])
			index = index - 1
			if value[index] == 1:
				continue
			if children[index] == []:
				value[index] = 1
				ones += 1
			else:
				lol = 1
				for j in children[index]:
					if value[j] == 0:
						lol = 0
						break
					lol = lol & value[j]
				if lol == 1:
					value[index] = 1
					ones += 1
		elif ones == N:
			print(N - 1)
		else:
			print(N - 1 - ones)


import queue

def _bfs(r, adj, parent, visited, chld):
	q = queue.Queue()
	q.put(r)
	while q.empty() is False:
		curr = q.get()
		visited[curr - 1] = True
		count = 0
		for child in adj[curr]:
			if visited[child - 1] is False:
				parent[child - 1] = curr
				visited[child - 1] = True
				q.put(child)
				count += 1
		chld[curr - 1] = count

def solve(n, edges, q, queries):
	adj = {}
	for (a, b) in edges:
		if a not in adj:
			adj[a] = [b]
		else:
			adj[a].append(b)
		if b not in adj:
			adj[b] = [a]
		else:
			adj[b].append(a)
	values = [0 for i in range(n)]
	parent = [-1 for i in range(n)]
	visited = [False for i in range(n)]
	child = [0 for i in range(n)]
	_bfs(1, adj, parent, visited, child)
	ans = n - 1
	for qu in queries:
		if qu[0] == 1:
			node = qu[1]
			if values[node - 1] == 1 or child[node - 1] > 0:
				continue
			else:
				child[parent[node - 1] - 1] -= 1
				values[node - 1] = 1
				if ans > 0:
					ans -= 1
		elif values[0] == 1:
			print(n - 1)
		else:
			print(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	edges = []
	for i in range(n - 1):
		edges.append([int(x) for x in input().split()])
	q = int(input())
	queries = []
	for i in range(q):
		queries.append([int(x) for x in input().split()])
	solve(n, edges, q, queries)


from collections import deque
for tea in range(int(input())):
	n = int(input())
	conn = dict()
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		if a in conn:
			conn[a].append(b)
		else:
			conn[a] = [b]
		if b in conn:
			conn[b].append(a)
		else:
			conn[b] = [a]
	parent = [-1 for i in range(n)]
	children = [[] for i in range(n)]
	bfs = deque([0])
	while True:
		try:
			lol = bfs.popleft()
		except:
			break
		for i in conn[lol]:
			if i != parent[lol]:
				parent[i] = lol
				children[lol].append(i)
				bfs.append(i)
	values = [0 for i in range(n)]
	oneCount = 0
	for queue in range(int(input())):
		prompt = [int(x) for x in input().split()]
		if prompt[0] == 1:
			if values[prompt[1] - 1] == 1 or oneCount < len(children[prompt[1] - 1]):
				continue
			lol = 1
			for i in children[prompt[1] - 1]:
				lol = lol & values[i]
			if lol == 1:
				oneCount += 1
			values[prompt[1] - 1] = lol
		elif oneCount == n:
			print(n - 1)
		else:
			print(n - 1 - oneCount)


def dfs(curr, adj, par, child):
	for elem in adj[curr]:
		if par[elem] != -1:
			continue
		par[elem] = curr
		child[curr].append(elem)
		dfs(elem, adj, par, child)
for i in range(int(input())):
	n = int(input())
	val = [0] * n
	adj = []
	child = []
	for j in range(n):
		adj.append([])
		child.append([])
	for j in range(n - 1):
		(s, d) = map(int, input().split())
		adj[s - 1].append(d - 1)
		adj[d - 1].append(s - 1)
	good = n - 1
	par = [-2] + [-1] * (n - 1)
	dfs(0, adj, par, child)
	for q in range(int(input())):
		ask = list(map(int, input().split()))
		if ask[0] == 2:
			print(good % n)
		else:
			node = ask[1] - 1
			if val[node] == 1:
				continue
			if len(child[node]) == 0:
				val[node] = 1
				good -= 1
			else:
				change = True
				for elem in child[node]:
					if val[elem] == 0:
						change = False
						break
				if change:
					good -= 1
					val[node] = 1


for _ in range(int(input())):
	n = int(input())
	graph = [dict() for _ in range(n + 1)]
	cnt = [0] * (n + 1)
	cnt[1] = 1
	graph[0][1] = True
	graph[1][0] = True
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		cnt[u] += 1
		cnt[v] += 1
		graph[u][v] = True
		graph[v][u] = True
	ans = n - 1
	for _ in range(int(input())):
		inp = [int(x) for x in input().split()]
		if len(inp) > 1:
			node = inp[1]
			if cnt[node] > 0:
				if cnt[node] == 1:
					pnode = None
					for i in graph[node].keys():
						pnode = i
					graph[pnode].pop(node)
					cnt[node] -= 1
					cnt[pnode] -= 1
					if node == 1:
						ans = n - 1
					else:
						ans -= 1
		else:
			print(ans)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *
import sys

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1, pi) = (1000000007, 998244353, 3.141592653589793)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(1, how_much_noob_I_am + 1):
		n = inpu()
		d = defaultdict(list)
		indegree = defaultdict(int)
		par = [-1] * (n + 1)
		q = deque()
		q.append([1, -1])
		for i in range(n - 1):
			(a, b) = sep()
			d[a].append(b)
			d[b].append(a)
			indegree[a] += 1
			indegree[b] += 1
		while q:
			(s, p) = q.popleft()
			for j in d[s]:
				if j == p:
					continue
				par[j] = s
				q.append([j, s])
		curr = set()
		for i in range(2, n + 1):
			if indegree[i] == 1:
				curr.add(i)
		q = inpu()
		tot = set()
		for i in range(q):
			l = lis()
			if l[0] == 1:
				if l[1] in curr:
					tot.add(l[1])
					curr.remove(l[1])
					if par[l[1]] == -1:
						continue
					indegree[par[l[1]]] -= 1
					if par[l[1]] == 1:
						if indegree[par[l[1]]] == 0:
							curr.add(par[l[1]])
					elif indegree[par[l[1]]] == 1:
						curr.add(par[l[1]])
			else:
				if len(tot) == n:
					print(n - 1)
					continue
				print(n - 1 - len(tot))
main()


T = int(input())
for _ in range(T):
	V = int(input())
	val = {i + 1: 0 for i in range(V)}
	E = []
	P = {i + 1: -1 for i in range(V)}
	C = {i + 1: [] for i in range(V)}
	A = {i + 1: [] for i in range(V)}
	for i in range(V - 1):
		(u, v) = (int(j) for j in input().split())
		E.append((u, v))
		A[u].append(v)
		A[v].append(u)
	vis = {i + 1: False for i in range(V)}
	qu = [1]
	while len(qu) != 0:
		v = qu[-1]
		qu.pop()
		vis[v] = True
		for u in A[v]:
			if not vis[u]:
				qu.append(u)
				C[v].append(u)
				P[u] = v
	Q = int(input())
	gE = [True] * (V - 1)
	gEn = V - 1
	for i in range(Q):
		inpQ = [int(j) for j in input().split()]
		if inpQ[0] == 1:
			u = inpQ[1]
			if len(C[u]) == 0:
				if val[u] == 1:
					continue
				if val[u] == 0:
					val[u] = 1
					gEn -= 1
			else:
				new_val = 1
				for c in C[u]:
					if val[c] == 0:
						new_val = 0
						break
				if new_val == val[u]:
					continue
				else:
					val[u] = 1
					if u == 1:
						gEn = V - 1
					else:
						gEn -= 1
		if inpQ[0] == 2:
			print(gEn)


T = int(input())

def dfs1(cur, adj, cnt, parents):
	ccnt = 0
	for c in adj[cur]:
		if parents[cur] == c:
			continue
		parents[c] = cur
		ccnt += dfs1(c, adj, cnt, parents)
	cnt[cur] = ccnt
	return 1
for t in range(T):
	n = int(input())
	adj = [[] for _ in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	cnt = [0 for _ in range(n + 1)]
	parents = [0 for _ in range(n + 1)]
	dfs1(1, adj, cnt, parents)
	Q = int(input())
	gcnt = n - 1
	all_one = [False] * (n + 1)
	for q in range(Q):
		cmd = list(map(int, input().split()))
		if cmd[0] == 1:
			cur = cmd[1]
			if cnt[cur] == 0 and (not all_one[cur]):
				cnt[parents[cur]] -= 1
				gcnt -= 1
				all_one[cur] = True
		else:
			print(n - 1 if all_one[1] else gcnt)