Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

A *directed tree* is a directed graph such that if all edges were undirected, this graph would be a tree. A *rooted directed tree* is a directed tree in which there is one vertex (the *root*, let's denote it by $r$) such that it is possible to reach all vertices of the graph from $r$ by moving along the directed edges.

You are given a directed tree with $N$ vertices (numbered $1$ through $N$). You may perform the following operation on it any number of times (including zero):
Choose some edge which currently exists in the graph.
Remove this edge.
Add a new edge in such a way that the graph becomes a directed tree again.

What is the smallest number of operations which need to be performed in order to make the directed tree rooted?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that there is a directed edge from $u$ to $v$ in the tree.

------  Output ------
For each test case, print a single line containing one integer ― the smallest number of operations we need to perform to create a rooted directed tree.

------  Constraints ------
$1 ≤ N ≤ 10^{4}$
$1 ≤ u, v ≤ N$
the graph described on the input is a directed tree
the sum of $N$ over all test cases does not exceed $10^{5}$

------  Subtasks ------
Subtask #1 (20 points): for each edge, $u = 1$ or $v = 1$ (the graph is a directed star)

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
2

3

1 2

3 2

3

1 2

2 3
----- Sample Output 1 ------ 
1

0
----- explanation 1 ------ 
Example case 1: We can delete the edge from vertex $3$ to vertex $2$ and insert an edge from $3$ to $1$. Then, the graph becomes a rooted directed tree with vertex $3$ as the root. However, there are many other possible solutions.

Example case 2: The graph is already a rooted directed tree; the root is vertex $1$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Directed graphs

Constructive algorithms

Data structures

Ad-hoc


Solutions:
for _ in range(int(input())):
	N = int(input())
	noparent = [True] * (N + 1)
	z = N
	for i in range(N - 1):
		(u, v) = list(map(int, input().split()))
		if noparent[v]:
			z -= 1
			noparent[v] = False
	print(z - 1)


for t in range(int(input())):
	n = int(input())
	l = [[]] * n
	d = [0] * n
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		l[u - 1] = v - 1
		d[v - 1] += 1
	res = 0
	for i in d:
		if i > 1:
			res += i - 1
	print(res)


def main():
	T = int(input())
	for counter in range(T):
		n = int(input())
		mat = [[0 for i in range(n)] for j in range(n)]
		e_in = [0 for i in range(n)]
		count = 0
		for i in range(n - 1):
			temp = list(map(int, input().split()))
			mat[temp[0] - 1][temp[1] - 1] = 1
			e_in[temp[1] - 1] += 1
		for items in e_in:
			if items == 0:
				count += 1
		print(count - 1)
main()


for _ in range(int(input())):
	n = int(input())
	indegrees = [0] * (n + 1)
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		indegrees[y] += 1
	c = 0
	for i in range(1, n + 1):
		if indegrees[i] == 0:
			c += 1
	print(c - 1)


T = int(input())
for n in range(0, T, 1):
	ele = int(input())
	arrCountNode = [0] * ele
	for j in range(0, ele - 1, 1):
		(a, b) = map(int, input().split())
		arrCountNode[b - 1] += 1
	print(arrCountNode.count(0) - 1)


t = int(input())
for i in range(t):
	n = int(input())
	arr_count_num = [0] * n
	for j in range(0, n - 1, 1):
		(u, v) = map(int, input().split())
		arr_count_num[v - 1] += 1
	print(arr_count_num.count(0) - 1)


T = int(input())
for _ in range(T):
	n = int(input())
	array = [0] * n
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		array[b - 1] += 1
	x = array.count(0) - 1
	print(x)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [0 for x in range(n)]
	ans = 0
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		arr[v - 1] += 1
	ans = 0
	for i in arr:
		ans += max(0, i - 1)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	array = [0 for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		array[v - 1] += 1
	print(str(array.count(0) - 1) + '\n')


t = int(input())
for i in range(t):
	n = int(input())
	p = [0] * (n + 1)
	ans = 0
	for j in range(n - 1):
		(u, v) = map(int, input().split())
		if p[v]:
			ans += 1
		else:
			p[v] = u
	print(ans)


t = int(input())
for i in range(t):
	ans = 0
	n = int(input())
	f = [0] * (n + 1)
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		f[y - 1] += 1
	for i in range(n):
		if f[i] > 1:
			ans = ans + (f[i] - 1)
	print(ans)


T = int(input())
for test in range(T):
	n = int(input())
	adj = []
	for i in range(n):
		adj.append([])
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v - 1)
	indeg = [0] * n
	for i in range(n):
		for j in adj[i]:
			indeg[j] += 1
	cnt = 0
	for i in range(n):
		if indeg[i] == 0:
			cnt += 1
	print(cnt - 1)


for _ in range(int(input())):
	n = int(input())
	adj = [True] * n
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[v - 1] = False
	print(adj.count(True) - 1)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	edgeToV = {}
	op = 0
	for _ in range(n - 1):
		(u, v) = map(int, sys.stdin.readline().split())
		if not edgeToV.get(v, 0):
			edgeToV[v] = 1
		else:
			op += 1
	print(op)


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 6)

def dfs(p):
	visited[p] = True
	for i in child[p]:
		dfs(i)

def absparent(u):
	while parent[u] != -1:
		u = parent[u]
	return u
for T in range(int(input())):
	n = int(input())
	child = [[] for i in range(n + 1)]
	parent = [-1] * (n + 1)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		child[u].append(v)
		parent[v] = u
	ans = -1
	visited = [False] * (n + 1)
	for i in range(1, n + 1):
		if not visited[i]:
			ans += 1
			dfs(absparent(i))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	v = set()
	for i in range(n - 1):
		t = list(map(int, input().split()))
		v.add(t[1])
	print(n - 1 - len(v))


T = int(input())
for i in range(T):
	n = int(input())
	vertices = set()
	for i in range(n - 1):
		temp = list(map(int, input().split()))
		vertices.add(temp[1])
	print(n - 1 - len(vertices))


from collections import defaultdict

def addEdge(u, v):
	adjlist[u].append(v)

def dfs(strt, ans):
	if visited[strt] == 0:
		ans[0] += 1
	visited[strt] = 0
	for i in adjlist[strt]:
		dfs(i, ans)
for _ in range(int(input())):
	n = int(input())
	adjlist = defaultdict(list)
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		addEdge(a, b)
	visited = [1] * (n + 1)
	visited[0] = 0
	ans = [0]
	for (key, value) in adjlist.items():
		for j in value:
			if visited[j] == 0:
				ans[0] += 1
			visited[j] = 0
	print(ans[0])


t = int(input())
while t > 0:
	n = int(input())
	l1 = [0 for i in range(n)]
	for i in range(n - 1):
		l2 = str(input()).split(' ')
		if l1[int(l2[1]) - 1] == 0:
			l1[int(l2[1]) - 1] = 1
	print(n - sum(l1) - 1)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = [0] * (n + 1)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		arr[v] += 1
	count = 0
	for i in range(1, n + 1):
		if arr[i] == 0:
			count += 1
	print(count - 1)


for _ in range(int(input())):
	n = int(input())
	x = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		x[v - 1].append(u - 1)
	ans = -1
	for i in x:
		if len(i) == 0:
			ans += 1
	print(ans)


t = int(input())
while t:
	n = int(input())
	a = []
	c = -1
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		a.append(y)
	for i in range(1, n + 1):
		if i not in a:
			c += 1
	print(c)
	t -= 1


import collections
import sys
sys.setrecursionlimit(10 ** 8)

class Graph:

	def __init__(self, v, e):
		self.v = v
		self.e = e
		self.graph = collections.defaultdict(list)
		self.indeg = {k: 0 for k in range(1, self.v + 1)}

	def add_node(self, a, b):
		self.graph[a].append(b)
		self.indeg[b] += 1

	def count_root(self):
		res = 0
		for (k, v) in self.indeg.items():
			if v == 0:
				res += 1
		return res - 1
for _ in range(int(input())):
	n = int(input())
	g = Graph(v=n, e=n - 1)
	for _ in range(1, n):
		(u, v) = map(int, input().split())
		g.add_node(u, v)
	print(g.count_root())


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		l.append(b)
	v = list(Counter(l).values())
	k = sum(v) - len(v)
	print(k)


t = int(input())
for _ in range(0, t):
	n = int(input())
	a = []
	b = []
	cnt = n
	for i in range(1, n + 1):
		b.append(i)
	for i in range(0, n - 1):
		(l, m) = map(int, input().split())
		a.append([l, m])
	for i in range(0, n - 1):
		if a[i][1] in b:
			cnt -= 1
			b.remove(a[i][1])
	print(cnt - 1)


from collections import Counter
import string
import math
import sys
from fractions import Fraction

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))

def printDivisors(n):
	divisors = []
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				divisors.append(i)
			else:
				divisors.extend((i, n // i))
		i = i + 1
	return divisors

def countTotalBits(num):
	binary = bin(num)[2:]
	return len(binary)

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
for _ in range(vary(1)):
	n = vary(1)
	tree = [0 for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = vary(2)
		tree[v] += 1
	if tree[1:].count(0) == 1:
		print(0)
		continue
	print(tree[1:].count(0) - 1)


for t in range(int(input())):
	n = int(input())
	incoming = {i: 0 for i in range(1, n + 1)}
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		incoming[v] += 1
	cnt = 0
	for (i, j) in incoming.items():
		if j == 0:
			cnt += 1
	print(cnt - 1)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	indegree = defaultdict(int)
	for _ in range(n - 1):
		(i, j) = map(int, input().split())
		indegree[j] += 1
	result = 0
	for j in indegree.values():
		if j > 1:
			result += j - 1
	print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		arr.append(b)
	a = [0] * n
	for i in range(n):
		a[i] = i + 1
		c = 0
	for i in range(n):
		if a[i] not in arr:
			c += 1
	print(c - 1)


for i in range(int(input())):
	n = int(input())
	l = [0 for i in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		l[b - 1] += 1
	s = 0
	for i in range(n):
		if l[i] > 1:
			s += l[i] - 1
	print(s)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	v = []
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		v.append(b)
	count = 0
	d = dict(Counter(v))
	for ele in d:
		if d[ele] > 1:
			count += d[ele] - 1
	print(count)


from collections import Counter
ans = []
for i in range(int(input())):
	count = 0
	u_ls = []
	v_ls = []
	n = int(input())
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		u_ls.append(u)
		v_ls.append(v)
	sum_u = Counter(u_ls)
	sum_v = Counter(v_ls)
	for (key, value) in sum_v.items():
		if value > 1:
			count += value - 1
		else:
			continue
	ans.append(count)
print(*ans, sep='\n')


from collections import Counter
ans = []
for i in range(int(input())):
	count = 0
	U = []
	V = []
	N = int(input())
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		U.append(u)
		V.append(v)
	sumU = Counter(U)
	sumV = Counter(V)
	for (key, value) in sumV.items():
		if value > 1:
			count += value - 1
		else:
			continue
	ans.append(count)
print(*ans, sep='\n')


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		rarr = []
		ans = 0
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			rarr.append(v)
		for i in range(1, n + 1):
			if rarr.count(i) == 0:
				ans += 1
		print(ans - 1)
except EOFError:
	pass


for _ in range(int(input())):
	N = int(input())
	A = [0] * N
	for i in range(1, N):
		(X, Y) = [int(i) for i in input().split(' ')]
		A[Y - 1] += 1
	print(A.count(0) - 1)


for i in range(int(input())):
	n = int(input())
	g = [0] * (n + 1)
	for j in range(n - 1):
		(a, b) = map(int, input().split())
		g[b] = g[b] + 1
	sumo = 0
	for j in range(n + 1):
		if g[j] > 0:
			sumo = sumo + g[j] - 1
	print(sumo)


for _ in range(int(input())):
	n = int(input())
	indegree = [0 for v in range(n)]
	for __ in range(n - 1):
		(u, v) = map(int, input().split())
		indegree[v - 1] += 1
	cnt = 0
	for deg in indegree:
		if deg == 0:
			cnt += 1
	print(cnt - 1)


from sys import maxsize
for _ in range(int(input())):
	n = int(input())
	counts = [0] * n
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		counts[y - 1] += 1
	ans = 0
	for i in counts:
		if i == 0:
			ans += 1
	print(ans - 1)


try:
	for _ in range(int(input())):
		nodes = int(input())
		lst = [0] * (nodes + 1)
		for i in range(nodes - 1):
			(u, v) = list(map(int, input().split()))
			lst[v] += 1
		count = 0
		for i in range(1, nodes + 1):
			if lst[i] == 0:
				count += 1
		print(count - 1)
except EOFError as t:
	pass


for i in range(int(input())):
	n = int(input())
	ar = [0] * (n + 1)
	c = 0
	f = 1
	for j in range(n - 1):
		(x, y) = map(int, input().split())
		ar[y] = ar[y] + 1
	c = 0
	for j in range(1, n + 1):
		if ar[j] == 0:
			c = c + 1
	print(c - 1)


t = int(input())
for i in range(0, t):
	x = int(input())
	start = []
	end = []
	for j in range(0, x - 1):
		(u, v) = map(int, input().split())
		start.append(u)
		end.append(v)
	s = set(end)
	change = 0
	for i in s:
		change += end.count(i) - 1
	print(change)


for _ in range(int(input())):
	n = int(input())
	ind = [0] * n
	out = [0] * n
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		a = a - 1
		b = b - 1
		out[a] += 1
		ind[b] += 1
	total = 0
	for i in ind:
		if i == 0:
			total += 1
	print(total - 1) if total > 0 else print(total)


from sys import stdin, stdout
import math
from itertools import permutations, combinations
from collections import defaultdict
from bisect import bisect_left, bisect_right
mod = 1000000007

def L():
	return list(map(int, stdin.readline().split()))

def In():
	return map(int, stdin.readline().split())

def I():
	return int(stdin.readline())

def printIn(ob):
	return stdout.write(str(ob) + '\n')

def powerLL(n, p):
	result = 1
	while p:
		if p & 1:
			result = result * n % mod
		p = int(p / 2)
		n = n * n % mod
	return result

def myCode():
	n = I()
	vertex = [0] * n
	for _ in range(n - 1):
		(u, v) = In()
		vertex[v - 1] += 1
	print(vertex.count(0) - 1)

def main():
	for t in range(I()):
		myCode()
main()


import sys, collections, math, itertools

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

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

def input():
	return sys.stdin.readline().strip()
mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	d = [0] * n
	for i in range(n - 1):
		(x, y) = get_ints()
		y -= 1
		d[y] += 1
	d.sort()
	cnt = -1
	for i in range(n - 1):
		if d[i] == 0:
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	l = [0] * (n + 1)
	ans = 0
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		l[b] += 1
		if l[b] > 1:
			ans += 1
	print(ans)


t = int(input())
for x in range(t):
	ans = 0
	n = int(input())
	ind = [0] * (n + 1)
	for i in range(n - 1):
		entry = list(map(int, input().strip().split()))
		u = entry[0]
		v = entry[1]
		ind[v] += 1
	for i in range(1, n + 1):
		if ind[i] == 0:
			ans += 1
	print(ans - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	ind = [0 for _ in range(n + 1)]
	for i in range(n - 1):
		(x, y) = [int(z) for z in input().split()]
		ind[y] += n
	cnt = 0
	for key in range(1, n + 1):
		if ind[key] == 0:
			cnt += 1
	print(cnt - 1)


def solve():
	pass
t = int(input())
while t:
	t -= 1
	n = int(input())
	array = [0] * (n + 1)
	for i in range(n - 1):
		(u, v) = [int(i) for i in input().split()]
		array[v] += 1
	count = 0
	for i in array[1:]:
		if i == 0:
			count += 1
	print(count - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	d = []
	for i in range(n - 1):
		(u, v) = list(map(int, input().split()))
		d.append(v)
	s = set(d)
	c = 0
	for i in s:
		c += d.count(i) - 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = [0 for i in range(n)]
	sum = 0
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		a[v - 1] += 1
		if a[v - 1] > 1:
			sum += 1
	print(sum)


for _ in range(int(input())):
	n = int(input())
	indegrees = [0 for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		indegrees[v] += 1
	ans = 0
	for indegree in indegrees:
		if indegree > 1:
			ans += indegree - 1
	print(ans)


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')
t = int(input())
for i in range(t):
	n = int(input())
	d = defaultdict(int)
	for j in range(n - 1):
		(u, v) = map(int, input().split())
		d[v] += 1
	ans = 0
	for j in range(1, n + 1):
		ans += max(0, d[j] - 1)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [0] * (n + 1)
	for j in range(n - 1):
		(u, v) = list(map(int, input().split()))
		arr[v] += 1
	count = 0
	for j in range(1, n + 1):
		if arr[j] == 0:
			count += 1
	print(count - 1)


for i in range(int(input())):
	n = int(input())
	n -= 1
	deg = [0] * (n + 1)
	for i in range(n):
		(u, v) = list(map(int, input().split()))
		deg[v - 1] += 1
	c = 0
	for i in deg:
		c += max(i - 1, 0)
	print(c)


for tc in range(int(input())):
	n = int(input())
	l = [0 for i in range(n)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		l[y - 1] += 1
	count = 0
	for i in l:
		if i == 0:
			count += 1
	print(count - 1)


for _ in range(int(input())):
	res = 0
	n = int(input())
	ind = [0 for i in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		ind[b - 1] += 1
	if ind.count(0) != 1 or ind.count(1) != n - 1:
		for i in ind:
			if i > 1:
				res += i - 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	nodes = []
	ans = 0
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		nodes.append([a, b])
	rght = []
	for i in nodes:
		rght.append(i[1])
	setrght = set(rght)
	print(len(rght) - len(setrght))


for t in range(int(input())):
	n = int(input())
	tree = []
	for i in range(n):
		tree.append([])
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		tree[v - 1].append(u)
	count = 0
	for i in range(n):
		if len(tree[i]) > 1:
			count += len(tree[i]) - 1
		else:
			continue
	print(count)


try:
	t = int(input())
	while t:
		t = t - 1
		n = int(input())
		(vv, ans) = ([], 0)
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			if v in vv:
				ans += 1
			else:
				vv.append(v)
		print(ans)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	inDegree = dict()
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		if inDegree.get(v, -1) == -1:
			inDegree[v] = 1
		else:
			inDegree[v] += 1
	print(max(n - len(inDegree.keys()) - 1, 0))


for _ in range(int(input())):
	d = {}
	c = 0
	n = int(input())
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		if b in d:
			c += 1
		else:
			d[b] = a
	print(c)


for _ in range(int(input())):
	l = int(input())
	lst = []
	for i in range(l - 1):
		(a, b) = map(int, input().split())
		lst.append(b)
	clst = [i for i in range(1, l + 1)]
	cnt = 0
	for i in range(l):
		if clst[i] not in lst:
			cnt += 1
	print(cnt - 1)


try:
	for _ in range(int(input())):
		n = int(input())
		r = []
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			r.append(b)
		print(len(r) - len(set(r)))
except:
	pass


from sys import stdin, stdout
import math
from bisect import bisect_left
from collections import Counter, deque, defaultdict
L = lambda : list(map(int, stdin.readline().strip().split()))
M = lambda : map(int, stdin.readline().strip().split())
I = lambda : int(stdin.readline().strip())
S = lambda : stdin.readline().strip()
C = lambda : stdin.readline().strip().split()

def pr(a):
	return ' '.join(list(map(str, a)))

def solve():
	n = I()
	a = set()
	for i in range(n - 1):
		(u, v) = M()
		a.add(v)
	print(n - 1 - len(a))
for _ in range(I()):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	x = []
	m = []
	p = []
	d = {}
	c = 0
	for j in range(n - 1):
		l = [int(i) for i in input().split()]
		x.append(l)
	for j in range(n - 1):
		m.append(x[j][0])
		p.append(x[j][1])
	for j in range(n - 1):
		if m[j] not in p:
			d[m[j]] = 1
	print(len(d) - 1)


for _ in range(int(input())):
	lst1 = []
	n = int(input())
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		lst1.append([a, b])
	lst2 = []
	for i in lst1:
		lst2.append(i[1])
	s = set(lst2)
	count = 0
	for i in s:
		count += lst2.count(i) - 1
	print(count)


class graph:

	def __init__(self):
		self.vertices = set()
		self.edges = []
		self.adjacency_list = {}
		self.size = 0

	def add_vertex(self, n):
		if n not in self.vertices:
			self.vertices.add(n)
			self.adjacency_list[n] = []
			self.size += 1
		else:
			pass

	def add_edge(self, u, v):
		if v not in self.vertices:
			self.add_vertex(v)
		self.adjacency_list[v].append(u)
t = int(input())
for _ in range(t):
	N = int(input())
	edges = []
	g = graph()
	for i in range(N - 1):
		x = [int(y) for y in input().split()]
		g.add_edge(x[0], x[1])
	count = 0
	for vertices in g.adjacency_list.values():
		count += len(vertices)
	print(count - g.size)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(int)
	v = set()
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		d[y] += 1
		v.add(x)
		v.add(y)
	diff = v.difference(d.keys())
	print(len(diff) - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	u = list()
	v = list()
	for i in range(n - 1):
		(outward, inward) = input().split()
		u.append(int(outward))
		v.append(int(inward))
	s = abs(len(v) - len(set(v)))
	print(s)


for u in range(int(input())):
	n = int(input())
	l = []
	for i in range(n - 1):
		x = list(map(int, input().split()))
		l.append(x[1])
	c = 0
	for i in range(1, n + 1):
		if i not in l:
			c += 1
	print(c - 1)


import math
prime = [True for i in range(10 ** 6 + 1)]

def SieveOfEratosthenes(n):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
T = int(input())
for _ in range(0, T):
	n = int(input())
	cnt = n
	a = []
	b = []
	for i in range(1, n + 1):
		b.append(i)
	for i in range(0, n - 1):
		(u, v) = map(int, input().split())
		a.append([u, v])
	for i in range(0, n - 1):
		if a[i][1] in b:
			cnt -= 1
			b.remove(a[i][1])
	print(cnt - 1)


for _ in range(int(input())):
	N = int(input())
	indegree = [0] * (N + 1)
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		indegree[b] += 1
	print(indegree[1:].count(0) - 1)


for _ in range(int(input())):
	N = int(input())
	tree = []
	for i in range(N - 1):
		tree.append([int(x) for x in input().split()])
	indegrees = {x: 0 for x in range(1, N + 1)}
	for edge in tree:
		indegrees[edge[1]] += 1
	total = 0
	for i in indegrees.values():
		if i > 1:
			total += i - 1
	print(total)


for _ in range(int(input())):
	n = int(input())
	c = []
	for _ in range(n - 1):
		c.append(list(map(int, input().split())))
	d = [i[1] for i in c]
	print(n - len(set(d)) - 1)