One day Bob drew a tree, $\mathbf{T}$, with $n$ nodes and $n-1$ edges on a piece of paper. He soon discovered that parent of a node depends on the root of the tree. The following images shows an example of that:

Learning the fact, Bob invented an exciting new game and decided to play it with Alice. The rules of the game is described below:

Bob picks a random node to be the tree's root and keeps the identity of the chosen node a secret from Alice. Each node has an equal probability of being picked as the root.
Alice then makes a list of $\mathrm{~g~}$ guesses, where each guess is in the form u v and means Alice guesses that $parent(v)=u$ is true. It's guaranteed that an undirected edge connecting $\mbox{u}$ and $\boldsymbol{\nu}$ exists in the tree. 
For each correct guess, Alice earns one point. Alice wins the game if she earns at least $\boldsymbol{\mbox{k}}$ points (i.e., at least $\boldsymbol{\mbox{k}}$ of her guesses were true).

Alice and Bob play $\textit{q}$ games. Given the tree, Alice's guesses, and the value of $\boldsymbol{\mbox{k}}$ for each game, find the probability that Alice will win the game and print it on a new line as a reduced fraction in the format p/q.

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of different games. The subsequent lines describe each game in the following format:

The first line contains an integer, $n$, denoting the number of nodes in the tree.
The $n-1$ subsequent lines contain two space-separated integers, $\mbox{u}$ and $\boldsymbol{\nu}$, defining an undirected edge between nodes $\mbox{u}$ and $\boldsymbol{\nu}$. 
The next line contains two space-separated integers describing the respective values of $\mathrm{~g~}$ (the number of guesses) and $\boldsymbol{\mbox{k}}$ (the minimum score needed to win).
Each of the $\mathrm{~g~}$ subsequent lines contains two space-separated integers, $\mbox{u}$ and $\boldsymbol{\nu}$, indicating Alice guesses $parent(v)=u$.

Constraints

$1\leq q\leq5$
$1\leq n\leq10^5$
$1\leq u,v\leq n$
$1\leq g,k\leq10^5$
The sum of $n$ over all test cases won't exceed $2\times10^5$.
No two guesses will be identical. 

Scoring

For $25\%$ of the maximum score, $1\leq n\leq10^3$.
For $100\%$ of the maximum score, $1\leq n\leq10^5$.

Output Format

Print the probability as a reduced fraction in the format p/q.

Note: Print 0/1 if the probability is $\mbox{0}$ and print 1/1 if the probability is $\mbox{1}$.

Sample Input 0
2
4
1 2
1 3
3 4
2 2
1 2
3 4
3
1 2
1 3
2 2
1 2
1 3

Sample Output 0
1/2
1/3

Explanation 0

Alice and Bob play the following $g=2$ games:

Alice makes two guesses, $\left(1\quad2\right)$ and $\left(3\quad4\right)$ , meaning she guessed that $parent(2)=1$ and $parent(4)=3$. To win the game, at least $k=2$ of her guesses must be true.

In the diagrams below, you can see that at least $2$ guesses are true if the root of the tree is either node $\mbox{1}$ or $3$:

There are $4$ nodes in total and the probability of picking node $\mbox{1}$ or $3$ as the root is $\frac{2}{4}$, which reduces to $\frac{1}{2}$.

In this game, Alice only wins if node $\mbox{1}$ is the root of the tree. There are $3$ nodes in total, and the probability of picking node $\mbox{1}$ as the root is $\frac{1}{3}$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions:
import sys
adj = []
p = []

def dfs(v, par):
	ret = 0
	for u in p[v]:
		ret += +1 if par == u else 0
	for u in adj[v]:
		if u != par:
			ret += dfs(u, v)
	return ret

def dfs2(v, par, cur, lim):
	if par != -1:
		for u in p[par]:
			if u == v:
				cur += 1
	for u in p[v]:
		if u == par:
			cur -= 1
	ret = cur >= lim
	for u in adj[v]:
		if u != par:
			ret += dfs2(u, v, cur, lim)
	return ret

def gcd(a, b):
	return gcd(b % a, a) if a > 0 else b
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	adj = [[] for _ in range(n)]
	p = [[] for _ in range(n)]
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		u -= 1
		v -= 1
		p[v].append(u)
	cur = dfs(0, -1)
	ans = dfs2(0, -1, cur, k)
	d = gcd(ans, n)
	ans = ans // d
	n = n // d
	print('%d/%d' % (ans, n))


import sys
from collections import defaultdict
from fractions import gcd
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	edges = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		edges[u].append(v)
		edges[v].append(u)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	guess_edges = set()
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		guess_edges.add((u, v))
	stack = [(1, 1)]
	res = 0
	while stack:
		(node, parent) = stack.pop()
		for child in edges[node]:
			if child == parent:
				continue
			if (node, child) in guess_edges:
				res += 1
			stack.append((child, node))
	stack = [(1, 1, res)]
	num_wins = 0
	while stack:
		(node, parent, res) = stack.pop()
		if res >= k:
			num_wins += 1
		for child in edges[node]:
			res2 = res
			if child == parent:
				continue
			if (node, child) in guess_edges:
				res2 -= 1
			if (child, node) in guess_edges:
				res2 += 1
			stack.append((child, node, res2))
	d = gcd(num_wins, n)
	print(str(num_wins // d) + '/' + str(n // d))


from fractions import Fraction

def score(graph, root, edges):
	visited = {root}
	queue = [root]
	parent = {root: None}
	while queue:
		curr = queue.pop(0)
		for v in graph[curr]:
			if v not in visited:
				visited.add(v)
				queue.append(v)
				parent[v] = curr
	return sum((1 if parent[e[1]] == e[0] else 0 for e in edges))

def all_scores(graph, edges, k):
	root = next(iter(graph))
	visited = {root}
	queue = [root]
	value = {root: score(graph, root, edges)}
	while queue:
		curr = queue.pop(0)
		for v in graph[curr]:
			if v not in visited:
				visited.add(v)
				queue.append(v)
				value[v] = value[curr]
				if (v, curr) in edges:
					value[v] += 1
				if (curr, v) in edges:
					value[v] -= 1
	return sum((1 if value[v] >= k else 0 for v in graph))
for _ in range(int(input())):
	n = int(input())
	graph = {}
	for i in range(n - 1):
		(u, v) = [int(a) for a in input().split()]
		if u in graph:
			graph[u].add(v)
		else:
			graph[u] = {v}
		if v in graph:
			graph[v].add(u)
		else:
			graph[v] = {u}
	(g, k) = [int(a) for a in input().split()]
	edges = set()
	for i in range(g):
		edges.add(tuple((int(a) for a in input().split())))
	res = Fraction(all_scores(graph, edges, k), n)
	if res == 0:
		print('0/1')
	elif res == 1:
		print('1/1')
	else:
		print(res)


import sys
from fractions import gcd

class TreeNode(object):

	def __init__(self, Ind):
		self.P = None
		self.Pa = None
		self.Children = []
		self.ChildTemp = []
		self.Ind = Ind

def RevisedFlood(ConnDict, GuessSet, n, k):
	WinCount = 0
	FireCount = [None for m in range(n)]
	ConnDictCopy = {m1: [m2 for m2 in ConnDict[m1]] for m1 in range(n)}
	for i1 in range(n):
		if len(ConnDictCopy[i1]) == 1:
			StartNode = i1
			break
	TreeList = [TreeNode(m) for m in range(n)]
	Visited = {StartNode}
	StartPoints = {StartNode}
	StartPointsNew = set()
	TravelSet = set()
	while len(Visited) < n:
		for i1 in StartPoints:
			for i2 in ConnDict[i1]:
				if i2 not in Visited:
					TravelSet.add((i1, i2))
					StartPointsNew.add(i2)
					Visited.add(i2)
		StartPoints = StartPointsNew
		StartPointsNew = set()
	for i1 in TravelSet:
		P = i1[0]
		C = i1[1]
		TreeList[P].Children.append(C)
		assert TreeList[C].P == None
		TreeList[C].P = P
	Root = TreeList[StartNode]
	nRev = [0 for m in range(n)]
	for i1 in TreeList:
		for i2 in i1.Children:
			i1.ChildTemp.append(i2)
	for i1 in range(n):
		if i1 != StartNode:
			TreeList[i1].Pa = TreeList[TreeList[i1].P]
	Current = Root
	while True:
		if len(Current.ChildTemp) == 0:
			if Current.P == None:
				break
			if (Current.P, Current.Ind) in GuessSet:
				nRev[Current.P] += GuessSet[Current.P, Current.Ind]
			nRev[Current.P] += nRev[Current.Ind]
			Current = TreeList[Current.P]
		else:
			Current = TreeList[Current.ChildTemp.pop()]
	for i1 in TreeList:
		for i2 in i1.Children:
			i1.ChildTemp.append(i2)
	PriorBranch = [StartNode]
	BranchRevAlongPath = [0]
	BranchForAlongPath = [0]
	ForAlongPath = 0
	RevAlongPath = 0
	FireCount[StartNode] = nRev[StartNode]
	if nRev[StartNode] >= k:
		WinCount += 1
	while True:
		if len(Current.ChildTemp) == 0:
			if Current.P == None:
				break
			if (Current.P, Current.Ind) in GuessSet:
				RevAlongPath -= GuessSet[Current.P, Current.Ind]
			if (Current.Ind, Current.P) in GuessSet:
				ForAlongPath -= GuessSet[Current.Ind, Current.P]
			Current = TreeList[Current.P]
			if len(Current.Children) > 1:
				BranchRevAlongPath.pop()
				BranchForAlongPath.pop()
				PriorBranch.pop()
		else:
			Current = TreeList[Current.ChildTemp.pop()]
			if len(Current.Pa.Children) > 1:
				BranchRevAlongPath.append(RevAlongPath)
				BranchForAlongPath.append(ForAlongPath)
				PriorBranch.append(Current.P)
			if len(Current.ChildTemp) == len(Current.Children):
				if (Current.P, Current.Ind) in GuessSet:
					RevAlongPath += GuessSet[Current.P, Current.Ind]
				if (Current.Ind, Current.P) in GuessSet:
					ForAlongPath += GuessSet[Current.Ind, Current.P]
				nFire = FireCount[PriorBranch[-1]] - (RevAlongPath - BranchRevAlongPath[-1]) + (ForAlongPath - BranchForAlongPath[-1])
				if nFire >= k:
					WinCount += 1
				FireCount[Current.Ind] = nFire
	if WinCount == 0:
		print('0/1')
		return
	G = gcd(WinCount, n)
	n /= G
	WinCount /= G
	print('%i/%i' % (WinCount, n))
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	ConnDict = {m: [] for m in range(n)}
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u) - 1, int(v) - 1]
		ConnDict[u].append(v)
		ConnDict[v].append(u)
	for i1 in ConnDict:
		ConnDict[i1].sort()
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	GuessSet = {}
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u) - 1, int(v) - 1]
		if GuessSet.get((u, v)) == None:
			GuessSet[u, v] = 1
		else:
			GuessSet[u, v] += 1
	RevisedFlood(ConnDict, GuessSet, n, k)


from collections import defaultdict
from collections import deque
import sys

def gcd(a, b):
	m = a // b
	r = a % b
	if r == 0:
		return b
	else:
		return gcd(b, r)
q = int(input().strip())
for a0 in range(q):
	n = int(input())
	points = [0] * n
	neigh = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = [int(x) - 1 for x in input().split()]
		neigh[u].append(v)
		neigh[v].append(u)
	(g, k) = [int(x) for x in input().split()]
	guessParent = defaultdict(list)
	for _ in range(g):
		(u, v) = [int(x) - 1 for x in input().split()]
		guessParent[v].append(u)
	leaf_ind = 0
	while len(neigh[leaf_ind]) > 1:
		leaf_ind += 1
	que = deque()
	que.append((leaf_ind, 0, False))
	extrapoint = 0
	found = set()
	while len(que) > 0:
		(nod, p, giveExtra) = que.popleft()
		if nod in found:
			continue
		found.add(nod)
		points[nod] += p
		if giveExtra:
			extrapoint += 1
		givePointTo = set(guessParent[nod])
		for gran in neigh[nod]:
			P = p
			giveExtra = False
			if gran in givePointTo:
				P += 1
			if nod in set(guessParent[gran]):
				P -= 1
				giveExtra = True
			que.append((gran, P, giveExtra))
	a = len([p for p in points if p + extrapoint >= k])
	b = n
	c = gcd(a, b)
	a //= c
	b //= c
	print(a, b, sep='/')


import sys
from fractions import gcd
from collections import defaultdict

class TreeNode:

	def __init__(self, number):
		self.number = number
		self.children = []
		self.score = None

def buildTree(E):
	nodes = [TreeNode(n + 1) for n in range(len(E))]
	for n in E.keys():
		nodes[n - 1].children += [nodes[next - 1] for next in E[n]]
	return nodes

def playAll(E, G):
	N = buildTree(E)

	def playFirst(root, prev=None):
		children = {child for child in root.children if prev != child}
		childrenNumbers = {e.number for e in children}
		score = sum((1 if u in childrenNumbers else 0 for u in G[root.number]))
		return score + sum((playFirst(child, root) for child in children))

	def play(root, prev):
		children = [child for child in root.children if prev != child]
		score = prev.score
		if prev.number in G[root.number]:
			score += 1
		if root.number in G[prev.number]:
			score -= 1
		root.score = score
		for child in children:
			play(child, root)
	N[0].score = playFirst(N[0])
	for child in N[0].children:
		play(child, N[0])
	return N
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	E = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		E[u].append(v)
		E[v].append(u)
	G = defaultdict(list)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		G[u].append(v)
	nodes = playAll(E, G)
	p = sum((1 if s.score >= k else 0 for s in nodes))
	d = gcd(p, n)
	print('%d/%d' % (p // d, n // d))


import sys
import fractions

def computeScore(V, cost):
	score = [None] * len(V)
	score[0] = 0
	stack = [0]
	while stack:
		x = stack.pop()
		for y in V[x]:
			if score[y] is None:
				score[y] = score[x]
				for (t, c) in cost[x]:
					if t == y:
						score[y] -= c
				stack.append(y)
	return score

def realScore(V, cost):
	seen = [False] * len(V)
	stack = [0]
	s0 = 0
	while stack:
		x = stack.pop()
		seen[x] = True
		for y in V[x]:
			if not seen[y]:
				for (t, c) in cost[x]:
					if t == y and c == 1:
						s0 += 1
				stack.append(y)
	return s0
q = int(input())
for a0 in range(q):
	n = int(input())
	V = [[] for i in range(n)]
	for a1 in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		V[u].append(v)
		V[v].append(u)
	(g, k) = map(int, input().split())
	cost = [[] for i in range(n)]
	for a1 in range(g):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		cost[u].append((v, 1))
		cost[v].append((u, -1))
	score = computeScore(V, cost)
	s0 = realScore(V, cost)
	p = 0
	for si in score:
		if si + s0 >= k:
			p += 1
	res = fractions.Fraction(p, n)
	if res == 1:
		print('1/1')
	elif res == 0:
		print('0/1')
	else:
		print(res)


import fractions
import sys

def BFS(root, adjMat):
	tovisit = []
	visited = []
	for i in range(n + 1):
		visited.append(False)
	output = []
	tovisit.append(root)
	while len(tovisit) > 0:
		curr = tovisit.pop()
		output.append(curr)
		visited[curr] = True
		for node in adjMat[curr]:
			if visited[node] == False:
				tovisit.append(node)
	return output

def changeBFS(root, adjMat):
	tovisit = []
	visited = []
	for i in range(n + 1):
		visited.append(False)
	output = []
	tovisit.append(root)
	while len(tovisit) > 0:
		curr = tovisit.pop()
		output.append(curr)
		visited[curr] = True
		for node in adjMat[curr]:
			if visited[node] == False:
				tovisit.append(node)
				change = 0
				if node in guesses[curr]:
					change -= 1
				if curr in guesses[node]:
					change += 1
				totals[node] = totals[curr] + change
	return output
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	adjacencies = []
	guesses = []
	for i in range(n + 1):
		adjacencies.append([])
		guesses.append([])
	for a1 in range(n - 1):
		(u, v) = list(map(int, input().strip().split(' ')))
		adjacencies[u].append(v)
		adjacencies[v].append(u)
	total = 0
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	guesslist = []
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		guesses[u].append(v)
		guesslist.append((u, v))
	tot = 0
	firstgame = BFS(1, adjacencies)
	indices = sorted(range(len(firstgame)), key=lambda k: firstgame[k])
	totals = [0 for i in range(n + 1)]
	initk = 0
	for q in range(g):
		if indices[guesslist[q][0] - 1] < indices[guesslist[q][1] - 1]:
			initk += 1
	totals[1] = initk
	changeBFS(1, adjacencies)
	tot = 0
	for i in range(len(totals)):
		if totals[i] >= k:
			tot += 1
	if tot == 0:
		print('0/1')
	elif tot == n:
		print('1/1')
	else:
		print(fractions.Fraction(tot, n))


import sys
import math
from collections import deque

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
Q = int(input().strip())
for _ in range(Q):
	N = int(input().strip())
	neighbours = [[] for _ in range(N + 1)]
	visited = [False for _ in range(N + 1)]
	parents = set()
	right_guesses = [0 for _ in range(N + 1)]
	for _ in range(N - 1):
		(u, v) = list(map(int, input().strip().split(' ')))
		neighbours[u] += [v]
		neighbours[v] += [u]
	(G, K) = list(map(int, input().strip().split(' ')))
	for _ in range(G):
		(u, v) = list(map(int, input().strip().split(' ')))
		parents.add((u, v))
	val = 0
	to_visit = deque([1])
	while to_visit:
		cur = to_visit.popleft()
		visited[cur] = True
		for v in neighbours[cur]:
			if not visited[v]:
				to_visit.append(v)
				if (cur, v) in parents:
					val += 1
	right_guesses[1] = val
	visited = [False for _ in range(N + 1)]
	to_visit = deque([1])
	while to_visit:
		cur = to_visit.popleft()
		visited[cur] = True
		for v in neighbours[cur]:
			delta = 0
			if not visited[v]:
				to_visit.append(v)
				if (cur, v) in parents:
					delta -= 1
				if (v, cur) in parents:
					delta += 1
				right_guesses[v] = right_guesses[cur] + delta
	cg = 0
	for i in range(1, N + 1):
		if right_guesses[i] >= K:
			cg += 1
	dv = gcd(cg, N)
	print('%d/%d' % (cg // dv, N // dv))


from collections import defaultdict, deque

def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
q = int(input())
for _ in range(q):
	n = int(input())
	edges = [tuple((int(x) - 1 for x in input().split())) for _ in range(n - 1)]
	E = defaultdict(list)
	for (a, b) in edges:
		E[a].append(b)
		E[b].append(a)
	leaf = None
	for node in E:
		if len(E[node]) == 1:
			leaf = node
			break
	(g, k) = map(int, input().split())
	guesses = (tuple((int(x) - 1 for x in input().split())) for _ in range(g))
	G = defaultdict(list)
	for (parent, child) in guesses:
		G[parent].append(child)
	pts = [0] * n
	visited = [False] * n
	Q = deque()
	Q.append((leaf, 0))
	corr = 0
	while Q:
		(cur, nseen) = Q.popleft()
		visited[cur] = True
		pts[cur] = nseen
		for neigh in E[cur]:
			neighseen = nseen
			if visited[neigh]:
				continue
			if cur in G:
				if neigh in G[cur]:
					neighseen -= 1
					corr += 1
			if neigh in G:
				if cur in G[neigh]:
					neighseen += 1
			Q.append((neigh, neighseen))
	num = sum((p + corr >= k for p in pts))
	den = n
	g = gcd(num, den)
	num //= g
	den //= g
	print(str(num) + '/' + str(den))


import sys

def gcd(a, b):
	r = a % b
	if r == 0:
		return b
	return gcd(b, r)

def getFraction(a, b):
	g = gcd(a, b)
	a /= g
	b /= g
	s = str(int(a)) + '/' + str(int(b))
	return s

def tranverse(node, adj, preorder, start, end, visited):
	preorder.append(node)
	visited.add(node)
	start[node] = len(preorder) - 1
	end[node] = len(preorder) - 1
	for child in adj[node]:
		if child not in visited:
			end[node] = tranverse(child, adj, preorder, start, end, visited)
	return end[node]
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	adj = [set() for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		adj[u].add(v)
		adj[v].add(u)
	preorder = []
	start = [0 for _ in range(n + 1)]
	end = [0 for _ in range(n + 1)]
	root = 1
	visited = set()
	tranverse(root, adj, preorder, start, end, visited)
	correct = [0 for _ in range(n + 1)]
	(g, k) = map(int, input().strip().split(' '))
	offset = 0
	for _ in range(g):
		(u, v) = map(int, input().strip().split(' '))
		if start[u] > start[v]:
			for i in range(start[u], end[u] + 1):
				correct[preorder[i]] += 1
		else:
			offset += 1
			for i in range(start[v], end[v] + 1):
				correct[preorder[i]] -= 1
	wins = 0
	for i in range(1, n + 1):
		if correct[i] + offset >= k:
			wins += 1
	print(getFraction(wins, n))


import sys

def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	tree = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u) - 1, int(v) - 1]
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	g_lst = [[] for _ in range(n)]
	for _ in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u) - 1, int(v) - 1]
		g_lst[u].append(v)
	score = 0
	rel_score = [0 for _ in range(n)]
	q_lst = [0]
	for i in range(n):
		cr_nd = q_lst[i]
		for child in tree[cr_nd]:
			tree[child].remove(cr_nd)
			rel_score[child] = rel_score[cr_nd]
			if child in g_lst[cr_nd]:
				score += 1
				rel_score[child] -= 1
			if cr_nd in g_lst[child]:
				rel_score[child] += 1
			q_lst.append(child)
	p = 0
	for el in rel_score:
		if el + score >= k:
			p += 1
	if p == 0:
		n = 1
	elif n % p == 0:
		n = n // p
		p = 1
	else:
		for i in range(2, p // 2 + 1):
			while p % i == 0 and n % i == 0:
				p = p // i
				n = n // i
	print('%d/%d' % (p, n))


import sys
from fractions import Fraction
from collections import deque
import random

def BuildTree(node, fa):
	try:
		c[node].remove(fa)
	except Exception:
		pass
	[BuildTree(x, node) for x in c[node]]
q = int(input().strip())
ans = 0
for a0 in range(q):
	n = int(input().strip())
	c = [deque() for _ in range(n)]
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		c[u - 1] += [v - 1]
		c[v - 1] += [u - 1]
	root = random.randint(0, n - 1)
	BuildTree(root, -1)
	(g, k) = input().strip().split(' ')
	(g, k) = (int(g), int(k))
	query = {}
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = (int(u) - 1, int(v) - 1)
		query[u, v] = query.get((u, v), 0) + 1
	ans = 0
	total = 0

	def BuildDp(node):
		return sum(map(BuildDp, c[node])) + sum(map(lambda x: query.get((node, x), 0), c[node]))

	def Calc(node, fa, upValue):
		upValue += -query.get((fa, node), 0) + query.get((node, fa), 0)
		count = total + upValue
		return (1 if count >= k else 0) + sum(map(lambda x: Calc(x, node, upValue), c[node]))
	total = BuildDp(root)
	ans = Calc(root, -1, 0)
	if ans == n:
		print('1/1')
	elif ans > 0:
		print(Fraction(ans, n))
	else:
		print('0/1')


import sys

def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	t = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u) - 1, int(v) - 1]
		t[u].append(v)
		t[v].append(u)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	g_lst = [[] for _ in range(n)]
	for _ in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u) - 1, int(v) - 1]
		g_lst[u].append(v)
	point = 0
	rel_point = [0 for _ in range(n)]
	q_lst = [0]
	for i in range(n):
		cr_nd = q_lst[i]
		for child in t[cr_nd]:
			t[child].remove(cr_nd)
			rel_point[child] = rel_point[cr_nd]
			if child in g_lst[cr_nd]:
				point += 1
				rel_point[child] -= 1
			if cr_nd in g_lst[child]:
				rel_point[child] += 1
			q_lst.append(child)
	p = 0
	for el in rel_point:
		if el + point >= k:
			p += 1
	if p == 0:
		n = 1
	elif n % p == 0:
		n = n // p
		p = 1
	else:
		for i in range(2, p // 2 + 1):
			while p % i == 0 and n % i == 0:
				p = p // i
				n = n // i
	print('%d/%d' % (p, n))


import sys
import fractions

def bfs(root):
	marked = [False for i in range(0, n)]
	stack = [root]
	marked[root - 1] = True
	result = set([])
	while len(stack) > 0:
		node = stack.pop()
		marked[node - 1] = True
		for neighbour in adj[node]:
			if not marked[neighbour - 1]:
				if (node, neighbour) in queries:
					result.add((node, neighbour))
				stack.append(neighbour)
	return result

def bfs2(root):
	marked = [False for i in range(0, n)]
	stack = [root]
	marked[root - 1] = True
	while len(stack) > 0:
		node = stack.pop()
		marked[node - 1] = True
		for neighbour in adj[node]:
			if not marked[neighbour - 1]:
				value = d[node]
				if (node, neighbour) in queries:
					value -= 1
				if (neighbour, node) in queries:
					value += 1
				d[neighbour] = value
				stack.append(neighbour)
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	adj = {i: [] for i in range(1, n + 1)}
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		adj[u].append(v)
		adj[v].append(u)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	queries = set([])
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		queries.add((u, v))
	count = 0
	d = {i: 0 for i in range(1, n + 1)}
	r = bfs(1)
	d[1] = len(r)
	bfs2(1)
	for e in d:
		if d[e] >= k:
			count += 1
	if float(count) / n == 0.0:
		print('0/1')
	elif float(count) / n == 1.0:
		print('1/1')
	else:
		print(fractions.Fraction(count, n))


import sys
import queue
import fractions

class Graph:

	def __init__(self, n):
		self.edge_list = dict()
		for i in range(1, n + 1):
			self.edge_list[i] = set()
		self.score = dict()

	def add_edge(self, u, v):
		self.edge_list[u].add(v)
		self.edge_list[v].add(u)

	def nbrs(self, u):
		return self.edge_list[u]

	def compute_score(self, root, guesses):
		start = 1
		q = queue.Queue()
		q.put(1)
		closed = set()
		self.score[root] = 0
		while not q.empty():
			node = q.get()
			closed.add(node)
			for nbr in self.nbrs(node):
				if nbr in closed:
					continue
				q.put(nbr)
				if (node, nbr) in guesses.keys():
					self.score[root] += guesses[node, nbr]

	def compute_scores(self, root, guesses):
		start = 1
		q = queue.Queue()
		q.put(1)
		closed = set()
		while not q.empty():
			node = q.get()
			closed.add(node)
			for nbr in self.nbrs(node):
				if nbr in closed:
					continue
				q.put(nbr)
				temp = self.score[node]
				if (node, nbr) in guesses.keys():
					temp -= guesses[node, nbr]
				if (nbr, node) in guesses.keys():
					temp += guesses[nbr, node]
				self.score[nbr] = temp

	def count_scores(self, k):
		return sum([x >= k for x in self.score.values()])
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	G = Graph(n)
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		G.add_edge(u, v)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	guesses = dict()
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		if (u, v) not in guesses:
			guesses[u, v] = 0
		guesses[u, v] += 1
	G.compute_score(1, guesses)
	G.compute_scores(1, guesses)
	count = G.count_scores(k)
	if count == 0:
		print('%d/%d' % (0, 1))
	else:
		temp = fractions.gcd(count, n)
		count //= temp
		n //= temp
		print('%d/%d' % (count, n))


import sys
MAXN = int(100000.0)
COUNT = 0

class Conn:

	def __init__(self, val, next):
		self.val = val
		self.next = next

	def print(self):
		print(self.val, self.next)

class Pool:

	def __init__(self):
		self.conns = [-1] * (2 * MAXN + 10)
		self.nodes = [-1] * (MAXN + 1)
		self.count = 0

	def connect(self, x, y):
		tmp = self.count
		self.count += 1
		self.conns[tmp] = Conn(y, self.nodes[x])
		self.nodes[x] = tmp

def traversal(cur, stop, guesses, pool):
	count = 0
	i = pool.nodes[cur]
	while i != -1:
		if pool.conns[i].val == stop:
			i = pool.conns[i].next
			continue
		if '%d-%d' % (cur, pool.conns[i].val) in guesses:
			count += 1
		count += traversal(pool.conns[i].val, cur, guesses, pool)
		i = pool.conns[i].next
	return count

def traversal1(cur, stop, guesses, hit, threshold, pool):
	if stop != -1 and '%d-%d' % (cur, stop) in guesses:
		hit += 1
	count = 1 if hit >= threshold else 0
	i = pool.nodes[cur]
	while i != -1:
		if pool.conns[i].val == stop:
			i = pool.conns[i].next
			continue
		found = 1 if '%d-%d' % (cur, pool.conns[i].val) in guesses else 0
		count += traversal1(pool.conns[i].val, cur, guesses, hit - found, threshold, pool)
		i = pool.conns[i].next
	return count

def solve(links, guesses, threshold, numNodes):
	guessDict = {}
	for g in guesses:
		(a, b) = g
		guessDict['%d-%d' % (a, b)] = g
	pool = Pool()
	for l in links:
		(x, y) = l
		pool.connect(x, y)
		pool.connect(y, x)
	hit = traversal(1, -1, guessDict, pool)
	count = traversal1(1, -1, guessDict, hit, threshold, pool)
	div = gcd(numNodes, count)
	return '%d/%d' % (count / div, numNodes / div)

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
q = int(input().strip())
for a0 in range(q):
	links = []
	guesses = []
	conns = [-1] * (2 * MAXN + 10)
	nodes = [-1] * (MAXN + 1)
	n = int(input().strip())
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		links.append([int(u), int(v)])
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		guesses.append([int(u), int(v)])
	threshold = k
	print(solve(links, guesses, threshold, n))


from fractions import gcd
q = int(input())
for qi in range(q):
	n = int(input())
	adj = [[] for i in range(n)]
	pGuess = [[] for i in range(n)]
	for i in range(n - 1):
		temp = input().split()
		u = int(temp[0]) - 1
		v = int(temp[1]) - 1
		adj[u].append(v)
		adj[v].append(u)
	temp = input().split()
	g = int(temp[0])
	k = int(temp[1])
	for i in range(g):
		temp = input().split()
		u = int(temp[0]) - 1
		v = int(temp[1]) - 1
		pGuess[v].append(u)
	kCurr = 0
	ks = [0 for i in range(n)]
	nodeQueue = [(0, -1)]
	while len(nodeQueue) > 0:
		t = nodeQueue.pop()
		u = t[0]
		p = t[1]
		if p in pGuess[u]:
			kCurr += 1
		for v in adj[u]:
			if v != p:
				nodeQueue.append((v, u))
	ks[0] = kCurr
	nodeQueue = [(0, 0)]
	while len(nodeQueue) > 0:
		t = nodeQueue.pop()
		u = t[0]
		p = t[1]
		ks[u] = ks[p]
		if p in pGuess[u]:
			ks[u] -= 1
		if u in pGuess[p]:
			ks[u] += 1
		for v in adj[u]:
			if v != p:
				nodeQueue.append((v, u))
	count = 0
	for ki in ks:
		if ki >= k:
			count += 1
	d = gcd(count, n)
	print(str(count // d) + '/' + str(n // d))


from collections import defaultdict, deque
from fractions import gcd

def read_line():
	return (int(x) for x in input().split())
for _ in range(int(input())):
	n = int(input())
	adj_matrix = defaultdict(dict)
	for (u, v) in (read_line() for _ in range(n - 1)):
		adj_matrix[u][v] = 0
		adj_matrix[v][u] = 0
	(g, k) = read_line()
	for (u, v) in (read_line() for _ in range(g)):
		adj_matrix[v][u] += 1
	order = []
	parent = [None] * (n + 1)
	root = next(iter(adj_matrix))
	que = deque([root])
	while que:
		node = que.popleft()
		order.append(node)
		for child in adj_matrix[node]:
			if child == parent[node]:
				continue
			parent[child] = node
			que.append(child)
	for node in reversed(order):
		if node == root:
			break
		p = parent[node]
		adj_matrix[node][p] += sum((adj_matrix[v][node] for v in adj_matrix[node] if v != p))
	result = 0
	for node in order:
		p = parent[node]
		total = sum((adj_matrix[v][node] for v in adj_matrix[node]))
		result += total >= k
		for v in adj_matrix[node]:
			adj_matrix[node][v] += total - adj_matrix[v][node]
	div = gcd(result, n)
	print('{}/{}'.format(result // div, n // div))


import sys
from fractions import gcd
from collections import defaultdict

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

def g_count(graph, gs, k):
	remain = [(0, 0)]
	gc = 0
	while remain:
		(prev, node) = remain.pop()
		for nn in graph[node]:
			if nn == prev:
				continue
			if (node, nn) in gs:
				gc += 1
			remain.append((node, nn))
	c_ok = 0
	remain = [(0, 0, gc)]
	while remain:
		(prev, node, gc) = remain.pop()
		if gc >= k:
			c_ok += 1
		for nn in graph[node]:
			if nn == prev:
				continue
			gc2 = gc
			if (node, nn) in gs:
				gc2 -= 1
			if (nn, node) in gs:
				gc2 += 1
			remain.append((node, nn, gc2))
	return c_ok
(q,) = readInts()
for _ in range(q):
	(n,) = readInts()
	graph = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = readInts()
		graph[u - 1].append(v - 1)
		graph[v - 1].append(u - 1)
	gs = set()
	(gn, k) = readInts()
	for _ in range(gn):
		(u, v) = readInts()
		gs.add((u - 1, v - 1))
	g_ok = g_count(graph, gs, k)
	if g_ok == 0:
		print('0/1')
	else:
		d = gcd(g_ok, n)
		print(''.join([str(g_ok // d), '/', str(n // d)]))


import sys
from io import StringIO
from collections import defaultdict, OrderedDict, namedtuple

class Graph(object):

	def __init__(self, adj_list):
		self.adj = adj_list
		self.lst_of_vertices = sorted(adj_list.keys())

	def adj_list(self, u):
		return self.adj[u] if self.adj.get(u) else []

	def bfs(self, source):
		parent = {source: None}
		frontier = [source]
		while frontier:
			nxt = []
			for u in frontier:
				for ch in self.adj_list(u):
					if ch and ch not in parent:
						parent[ch] = u
						nxt.append(ch)
			frontier = nxt
		return parent
KidParent = namedtuple('KidParent', ['kid', 'parent'])

def count_new_score(guessed_parents, cnt, old_root_kp, old_r_kp, new_root_kp, new_r_kp):
	if old_root_kp in guessed_parents:
		cnt -= 1
	if old_r_kp in guessed_parents:
		cnt -= 1
	if new_root_kp in guessed_parents:
		cnt += 1
	if new_r_kp in guessed_parents:
		cnt += 1
	return cnt

def count_correct_guesses_for_root(cnt, min_num_correct_guesses):
	return 1 if cnt >= min_num_correct_guesses else 0

def move_root_to_r(guessed_parents, cnt, r, root, parent):
	old_root_kp = KidParent(root, parent[root])
	old_r_kp = KidParent(r, parent[r])
	new_root_kp = KidParent(root, r)
	new_r_kp = KidParent(r, parent[root])
	(parent[root], parent[r]) = (r, parent[root])
	cnt = count_new_score(guessed_parents, cnt, old_root_kp, old_r_kp, new_root_kp, new_r_kp)
	return (parent, cnt)

def move_root_back_from_r(guessed_parents, cnt, r, root, parent):
	return move_root_to_r(guessed_parents, cnt, root, r, parent)

def count_correct_combinations_for_all_vertices(graph, guessed_parents, min_num_correct_guesses):
	first_root = graph.lst_of_vertices[0]
	parent_root = graph.bfs(first_root)
	parent = parent_root.copy()
	parent_set = set(parent.items())
	processed = set()
	root = first_root
	processed.add(root)
	cnt = len(guessed_parents & parent.items())
	cnt_success = 1 if cnt >= min_num_correct_guesses else 0
	(cnt_success, cnt) = count_success_in_tree(root, processed, graph, parent, guessed_parents, min_num_correct_guesses, cnt_success, cnt)
	return cnt_success

def count_success_in_tree(root, processed, graph, parent, guessed_parents, min_num_correct_guesses, cnt_success, cnt):
	g_adj_list = graph.adj_list
	processed_add = processed.add
	for r in g_adj_list(root):
		if r not in processed:
			processed_add(r)
			(parent, cnt) = move_root_to_r(guessed_parents, cnt, r, root, parent)
			cnt_success += count_correct_guesses_for_root(cnt, min_num_correct_guesses)
			(cnt_success, cnt) = count_success_in_tree(r, processed, graph, parent, guessed_parents, min_num_correct_guesses, cnt_success, cnt)
			(parent, cnt) = move_root_back_from_r(guessed_parents, cnt, r, root, parent)
	return (cnt_success, cnt)

def calculate_probability_of_winning(graph, guessed_parents, min_num_correct_guesses):
	cnt_success = count_correct_combinations_for_all_vertices(graph, guessed_parents, min_num_correct_guesses)
	s_prob_pair = reduce_ratio_of_ints_by_common_multipliers(cnt_success, len(graph.lst_of_vertices))
	success_probability = '%d/%d' % s_prob_pair
	return success_probability

def reduce_ratio_of_ints_by_common_multipliers(m, n):
	if m == n:
		return (1, 1)
	elif m == 0:
		return (0, 1)
	k = min(m, n)
	for j in range(k, 1, -1):
		if not m % j and (not n % j):
			m = m // j
			n = n // j
	return (m, n)

def enter_data():
	lines = sys.stdin.readlines()
	q = int(lines[0].strip(), 10)
	jn = 1
	for j in range(q):
		adj_list = defaultdict(set)
		guessed_parents = set()
		n = int(lines[jn].strip(), 10)
		for i in range(1, n):
			(u, v) = [(int(u.strip(), 10), int(v.strip(), 10)) for (u, v) in [tuple(lines[jn + i].split(' '))]][0]
			adj_list[u].add(v)
			adj_list[v].add(u)
		(g, k) = lines[jn + n].split(' ')
		(g, k) = [int(g.strip(), 10), int(k.strip(), 10)]
		gng = jn + n + 1
		for i in range(g):
			(u, v) = [(int(u.strip(), 10), int(v.strip(), 10)) for (u, v) in [tuple(lines[gng + i].split(' '))]][0]
			guessed_parents.add((v, u))
		graph = Graph(adj_list=adj_list)
		success_probability = calculate_probability_of_winning(graph, guessed_parents, min_num_correct_guesses=k)
		print(success_probability)
		jn += 1 + (n - 1) + 1 + g
enter_data()


from fractions import gcd
q = int(input())
for _ in range(q):
	n = int(input())
	graph = [[] for _ in range(n + 1)]
	guess = [[] for _ in range(n + 1)]
	todo = [False, False] + [True for _ in range(n - 1)]
	adjust = [0 for _ in range(n + 1)]
	(at_one, term, curr_node, dfs) = (0, True, 1, [1])
	for _ in range(n - 1):
		(u, v) = [int(_) for _ in input().split(' ')]
		graph[u].append(v)
		graph[v].append(u)
	(g, k) = [int(_) for _ in input().split(' ')]
	for _ in range(g):
		(u, v) = [int(_) for _ in input().split(' ')]
		if u in guess[v]:
			del guess[v][guess[v].index(u)]
			at_one += 1
		else:
			guess[u].append(v)
	while dfs:
		(term, curr_node) = (True, dfs[-1])
		for child in graph[curr_node]:
			if todo[child]:
				(todo[child], term) = (False, False)
				dfs.append(child)
				if child in guess[curr_node]:
					at_one += 1
					adjust[child] = adjust[curr_node] - 1
				elif curr_node in guess[child]:
					adjust[child] = adjust[curr_node] + 1
				else:
					adjust[child] = adjust[curr_node]
		if term:
			dfs.pop()
	wins = sum([score >= k for score in [at_one + adj for adj in adjust[1:]]])
	if wins == 0:
		print('0/1')
	else:
		divs = gcd(wins, n)
		print(str(wins // divs) + '/' + str(n // divs))


import sys
import sys
from collections import deque

def gcd(a, b):
	if b == 0 or a == 0:
		return 1
	(a, b) = (max(a, b), min(a, b))
	if a % b == 0:
		return b
	else:
		return gcd(b, a % b)

def findout(graph, guess):
	n = len(graph)
	C = [0 for i in range(n + 1)]

	def parents(graph):
		B = [-1 for i in range(n + 1)]
		queue = deque([1])
		while queue:
			vertex = queue.popleft()
			for x in set(graph[vertex]) - set({B[vertex]}):
				queue.append(x)
			for i in set(graph[vertex]) - set({B[vertex]}):
				B[i] = vertex
		return B
	P = parents(graph)
	tem = 0
	for Q in guess:
		[u, v] = Q
		if P[v] == u:
			if C[v] == 1:
				C[v] = 0
			else:
				C[v] = -1
			tem += 1
		elif P[u] == v:
			if C[u] == -1:
				C[u] = 0
			else:
				C[u] = 1
	temp = [-1 for i in range(n + 1)]
	temp[1] = tem
	queue = deque([1])
	while queue:
		vertex = queue.popleft()
		for x in set(graph[vertex]) - set({P[vertex]}):
			queue.append(x)
		for i in set(graph[vertex]) - set({P[vertex]}):
			temp[i] = temp[vertex] + C[i]
	return temp[1:]
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	graph = {}
	for i in range(1, n + 1):
		graph[i] = []
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		graph[u] += [v]
		graph[v] += [u]
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	guess = []
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		guess += [[u, v]]
	ans = findout(graph, guess)
	count = 0
	for i in range(len(ans)):
		if ans[i] >= k:
			count += 1
	T = gcd(count, n)
	if count == 0:
		print(0, end='')
		print('/', end='')
		print(1)
	else:
		print(count // T, end='')
		print('/', end='')
		print(n // T)


from collections import deque

class Node:

	def __init__(self):
		self.children = set()
		self.generations = []
		self.parent = None
		self.correct = 0
		self.accumulated = 0

def getElements(node, nodes):
	nodes[node].generations += nodes[node].children
	for node_i in nodes[node].children:
		getElements(node_i, nodes)
		nodes[node].generations += nodes[node_i].generations
q = int(input().strip())
for q_i in range(q):
	n = int(input().strip())
	nodes = [Node() for _ in range(n + 1)]
	for edge_i in range(n - 1):
		(u, v) = map(int, input().strip().split())
		nodes[u].children.add(v)
		nodes[v].children.add(u)
	queued = {1}
	nodes[1].parent = None
	queue = deque()
	queue.append(1)
	while queue:
		item = queue.popleft()
		for node_i in nodes[item].children:
			nodes[node_i].children.remove(item)
			nodes[node_i].parent = item
			if node_i not in queued:
				queue.append(node_i)
				queued.add(node_i)
	getElements(1, nodes)
	(g, k) = map(int, input().strip().split())
	guess_list = [map(int, input().strip().split()) for _ in range(g)]
	for guess in guess_list:
		(u, v) = guess
		if nodes[v].parent == u:
			nodes[v].correct -= 1
			nodes[1].correct += 1
		else:
			nodes[u].correct += 1
	wins = 0
	queued = {1}
	queue = deque()
	queue.append(1)
	nodes[1].accumulated = nodes[1].correct
	while queue:
		item = queue.popleft()
		if nodes[item].accumulated >= k:
			wins += 1
		for node_i in nodes[item].children:
			if node_i not in queued:
				queue.append(node_i)
				queued.add(node_i)
				nodes[node_i].accumulated = nodes[item].accumulated + nodes[node_i].correct
	if wins == 0:
		print('0/1')
	elif wins == n:
		print('1/1')
	else:
		dividend = n
		quotient = wins
		remainder = n % wins
		while remainder:
			dividend = quotient
			quotient = remainder
			remainder = dividend % quotient
		print(wins // quotient, '/', n // quotient, sep='')


import sys

def getone():
	return int(input())

def gettwo():
	return map(int, input().strip().split())

def addlink(a, b, graph):
	ks = graph.keys()
	if a in ks:
		graph[a].add(b)
	else:
		graph[a] = {b}
	if b in ks:
		graph[b].add(a)
	else:
		graph[b] = {a}
	return graph

def factorize(n):
	res = []
	i = 2
	while i <= n:
		while n % i == 0:
			res.append(i)
			n /= i
		i += 1
	if res == []:
		res = [n]
	return res

def common_multipliers(a, b):
	if a == 0:
		(resa, resb) = (0, 1)
	elif b == 0:
		(resa, resb) = (1, 0)
	else:
		fa = factorize(a)
		fb = factorize(b)
		cm = 1
		for bf in fb:
			if bf in fa:
				cm *= bf
				del fa[fa.index(bf)]
		(resa, resb) = (int(a / cm), int(b / cm))
	return (resa, resb)

def list_of_empty_sets(count):
	res = [set()]
	while len(res) < count:
		res.append(set())
	return res

def list_of_zeros(count):
	res = [0]
	while len(res) < count:
		res.append(0)
	return res

def initialize_group():
	return {'n_nodes': set(), 'pops': set(), 'kids': set(), 'kplus': 0}

def nodecount_with_groups(node, visited, current_region):
	visited.add(node)
	regions[current_region].add(node)
	groups[current_region]['n_nodes'].add(node)
	(gplus, gminus) = (0, 0)
	for n in graph[node] - visited:
		(cplus, cminus) = ((node, n) in guesses, (n, node) in guesses)
		next_region = current_region
		if cplus & cminus:
			guaranteed[0] += 1
		if cplus ^ cminus:
			cr[0] += 1
			groups[cr[0]] = initialize_group()
			if cplus:
				groups[cr[0]]['pops'].add(current_region)
				groups[current_region]['kids'].add(cr[0])
			if cminus:
				groups[cr[0]]['kids'].add(current_region)
				groups[current_region]['pops'].add(cr[0])
			next_region = cr[0]
			current_sign = int(cplus - cminus)
		(rplus, rminus) = nodecount_with_groups(n, visited, next_region)
		gplus += rplus + cplus
		gminus += rminus + cminus
	return (gplus, gminus)

def traverse_groups(group, visited_g):
	(pops, kids) = (groups[group]['pops'] - visited_g, groups[group]['kids'] - visited_g)
	for g in pops:
		traverse_groups(g, {group})
		groups[group]['kplus'] += groups[g]['kplus']
	for g in kids:
		traverse_groups(g, {group})
		groups[group]['kplus'] += groups[g]['kplus'] + 1

def traverse_kplus(group, visited_g):
	for g in groups[group]['pops'] - visited_g:
		groups[g]['kplus'] = groups[group]['kplus'] + 1
		traverse_kplus(g, {group})
	for g in groups[group]['kids'] - visited_g:
		groups[g]['kplus'] = groups[group]['kplus'] - 1
		traverse_kplus(g, {group})
q = getone()
for _ in range(q):
	Nodes = getone()
	graph = {}
	guaranteed = [0]
	for __ in range(Nodes - 1):
		(u, v) = gettwo()
		graph = addlink(u, v, graph)
	(g, k) = gettwo()
	all_guesses = set()
	back_guesses = set()
	for __ in range(g):
		(u, v) = gettwo()
		all_guesses.add((u, v))
		back_guesses.add((v, u))
	g0 = len(all_guesses)
	back_forth = all_guesses & back_guesses
	guesses = all_guesses - back_forth
	g = len(guesses)
	guaranteed[0] = int(len(back_forth) / 2)
	k -= guaranteed[0]
	regions = list_of_empty_sets(g + 1)
	cr = [0]
	groups = {0: initialize_group()}
	kplus = list_of_zeros(g + 1)
	for start in graph.keys():
		break
	nodecount_with_groups(start, {start}, 0)
	traverse_groups(0, set())
	traverse_kplus(0, set())
	kwinners = sum([len(groups[ks]['n_nodes']) for ks in groups.keys() if groups[ks]['kplus'] >= k])
	(kw, kb) = common_multipliers(kwinners, Nodes)
	print('%i/%i' % (kw, kb))


from fractions import Fraction as F
ES = set()
for _ in range(int(input())):
	n = int(input())
	g = {}
	q = {}
	for _ in range(1, n):
		(u, v) = map(int, input().split())
		g.setdefault(u, set()).add(v)
		g.setdefault(v, set()).add(u)
	(c, k) = map(int, input().split())
	p = set()
	for _ in range(c):
		(u, v) = map(int, input().split())
		p.add((u, v))

	def dfs(v, u=-1):
		z = 0
		for i in g.get(v, ES):
			if i != u:
				z += dfs(i, v) + int((v, i) in p)
		return z

	def propagate(x, v, u=-1):
		q[v] = x
		for i in g.get(v, ES):
			if i != u:
				propagate(x + int((i, v) in p) - int((v, i) in p), i, v)
	propagate(dfs(1), 1)
	print((lambda x: '%d/%d' % (x.numerator, x.denominator))(F(len(list(filter(lambda i: i >= k, q.values()))), n)))


def list_input():
	return tuple(map(int, input().strip().split()))

def dfs(edges, root):
	stack = [(root, v) for v in edges[root]]
	while stack:
		(u, v) = stack.pop()
		yield (u, v)
		stack.extend(((v, w) for w in edges[v] if w != u))

def solve(edges, guesses, k):
	root = 1
	base_score = 0
	scores = [None] * len(edges)
	scores[root] = 0
	for (u, v) in dfs(edges, root):
		scores[v] = scores[u]
		if (u, v) in guesses:
			base_score += guesses[u, v]
			scores[v] -= guesses[u, v]
		if (v, u) in guesses:
			scores[v] += guesses[v, u]
	return sum((1 for s in scores[1:] if s + base_score >= k))

def gcd(a, b):
	while a > 0:
		(a, b) = (b % a, a)
	return b
for q in range(int(input())):
	N = int(input())
	edges = [set() for _ in range(N + 1)]
	for _ in range(N - 1):
		(u, v) = list_input()
		edges[u].add(v)
		edges[v].add(u)
	(g, k) = list_input()
	guesses = dict()
	for _ in range(g):
		uv = list_input()
		guesses[uv] = guesses.get(uv, 0) + 1
	wins = solve(edges, guesses, k)
	d = gcd(wins, N)
	print(wins // d, N // d, sep='/')


from fractions import gcd

class NodeInfo:

	def __init__(self):
		self.connected_nodes = {}
		self.score = None

def get_edge_matched_answers(graph, node1_index, node2_index, answers):
	current_value = graph[node1_index].connected_nodes[node2_index]
	if current_value is not None:
		return current_value
	current_value = 0
	if (node1_index, node2_index) in answers:
		current_value += 1
	for adj_node_index in graph[node2_index].connected_nodes:
		if adj_node_index != node1_index:
			current_value += get_edge_matched_answers(graph, node2_index, adj_node_index, answers)
	graph[node1_index].connected_nodes[node2_index] = current_value
	return current_value

def process_node(graph, node_index, answers):
	current_node = graph[node_index]
	node_score = 0
	for adj_node_index in current_node.connected_nodes:
		node_score += get_edge_matched_answers(graph, node_index, adj_node_index, answers)
	graph[node_index].score = node_score

def calculate_suitable_root_nodes_count(graph, answers, min_score):
	for node_index in range(len(graph)):
		process_node(graph, node_index, answers)
	suitable_nodes_count = 0
	for node in graph:
		if node.score >= min_score:
			suitable_nodes_count += 1
	return suitable_nodes_count
games_number = int(input())
for game_index in range(games_number):
	nodes_number = int(input())
	graph = []
	for node_index in range(nodes_number):
		graph.append(NodeInfo())
	for edge_index in range(nodes_number - 1):
		edge = list(map(int, input().strip().split(' ')))
		u = edge[0] - 1
		v = edge[1] - 1
		graph[u].connected_nodes[v] = None
		graph[v].connected_nodes[u] = None
	(guesses_number, min_score) = input().strip().split(' ')
	(guesses_number, min_score) = [int(guesses_number), int(min_score)]
	answers = set()
	for guess_index in range(guesses_number):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u) - 1, int(v) - 1]
		answers.add((u, v))
	suitable_nodes_count = calculate_suitable_root_nodes_count(graph, answers, min_score)
	if suitable_nodes_count == 0:
		print('0/1')
	else:
		delimiter = gcd(nodes_number, suitable_nodes_count)
		print('{0}/{1}'.format(int(suitable_nodes_count / delimiter), int(nodes_number / delimiter)))


import sys

def solve(tree, gg, k):

	def gcd(a, b):
		while b:
			(a, b) = (b, a % b)
		return a

	def edge_gen(tree, root):
		marked = set()
		stack = [root]
		while stack:
			fr = stack.pop()
			marked.add(fr)
			for to in tree[fr]:
				if to not in marked:
					stack.append(to)
					yield (fr, to)

	def matches(tree, gg, root):
		cnt = 0
		for edge in edge_gen(tree, root):
			if edge in gg:
				cnt += 1
		return cnt

	def matches_gen(tree, gg):
		root = min(tree)
		cnt = matches(tree, gg, root)
		stack = [(root, cnt)]
		marked = set()
		while stack:
			(fr, cnt) = stack.pop()
			marked.add(fr)
			yield (fr, cnt)
			for to in tree[fr]:
				if to not in marked:
					(edge, redge) = ((fr, to), (to, fr))
					new_cnt = cnt
					if edge in gg:
						new_cnt -= 1
					if redge in gg:
						new_cnt += 1
					stack.append((to, new_cnt))
	print('tree: %s' % tree, file=sys.stderr)
	print('gg: %s' % gg, file=sys.stderr)
	(total, total_cnt) = (0, 0)
	for (node, cnt) in matches_gen(tree, gg):
		total += 1
		if cnt >= k:
			total_cnt += 1
		print('node=%d cnt=%d' % (node, cnt), file=sys.stderr)
	print('%d/%d' % (total_cnt, total), file=sys.stderr)
	g = gcd(total_cnt, total)
	return (total_cnt // g, total // g)
t = int(input())
for _ in range(t):
	tree = dict()
	n = int(input())
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		for (a, b) in ((u, v), (v, u)):
			if a in tree:
				tree[a].append(b)
			else:
				tree[a] = [b]
	(g, k) = map(int, input().split())
	gg = set()
	for _ in range(g):
		(u, v) = map(int, input().split())
		gg.add((u, v))
	(u, v) = solve(tree, gg, k)
	if u == 0:
		v = 1
	print('%d/%d' % (u, v))


def dfs1(graph, v, guesses, seen, guessed, count):
	cnt = count
	seen.add(v)
	guessed[v] += cnt
	for u in graph[v]:
		if u not in seen:
			if (u, v) in guesses:
				count += 1
			dfs1(graph, u, guesses, seen, guessed, count)
			if count > cnt:
				count -= 1

def dfs2(graph, v, guesses, seen, guessed, counts):
	count = 0
	seen.add(v)
	for u in graph[v]:
		if u not in seen:
			cnt = dfs2(graph, u, guesses, seen, guessed, counts)
			if (v, u) in guesses:
				cnt += 1
			count += cnt
	counts[v] = count
	guessed[v] += count
	return count

def dfs3(graph, v, guesses, seen, guessed, count, counts):
	seen.add(v)
	guessed[v] += count
	for u in graph[v]:
		if u not in seen:
			cnt = counts[v] - counts[u] + count
			if (v, u) in guesses:
				cnt -= 1
			dfs3(graph, u, guesses, seen, guessed, cnt, counts)
q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	graph = {}
	for _ in range(n - 1):
		(u, v) = [int(x) for x in input().strip().split()]
		if u not in graph:
			graph[u] = []
		if v not in graph:
			graph[v] = []
		graph[u].append(v)
		graph[v].append(u)
	(g, k) = [int(x) for x in input().strip().split()]
	guesses = set()
	for _ in range(g):
		(u, v) = [int(x) for x in input().strip().split()]
		guesses.add((u, v))
	guessed = [0 for _ in range(n + 1)]
	counts = [0 for _ in range(n + 1)]
	dfs1(graph, 1, guesses, set(), guessed, 0)
	dfs2(graph, 1, guesses, set(), guessed, counts)
	dfs3(graph, 1, guesses, set(), guessed, 0, counts)
	(x, y) = (0, n)
	for v in guessed[1:]:
		if v >= k:
			x += 1
	from math import gcd
	d = gcd(x, y)
	print('{}/{}'.format(x // d, y // d))


import sys
import fractions

def DFS1(root, p=None):
	result[root] = 0
	for child in adj[root]:
		if p is None or child != p:
			result[root] += DFS1(child, root)
			if parent.get(child) is not None and parent[child].get(root) is not None:
				result[root] += 1
	return result[root]

def DFS2(root, p=None):
	if p is not None:
		diff = 0
		if parent.get(root) is not None and parent[root].get(p) is not None:
			diff -= 1
		if parent.get(p) is not None and parent[p].get(root) is not None:
			diff += 1
		result[root] = result[p] + diff
	for c in adj[root]:
		if p is None or c != p:
			DFS2(c, root)

def add_node(m, a, b):
	if m.get(a) is None:
		m[a] = list()
	m[a].append(b)

def _add_node(m, a, b):
	if m.get(a) is None:
		m[a] = dict()
	m[a][b] = True

def reduce(a, b):
	return str(a // fractions.gcd(a, b)) + '/' + str(b // fractions.gcd(a, b))
q = int(input().strip())
for a0 in range(q):
	adj = dict()
	parent = dict()
	result = dict()
	n = int(input().strip())
	r = 0
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		add_node(adj, u, v)
		add_node(adj, v, u)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		_add_node(parent, v, u)
		r = v
	DFS1(r)
	DFS2(r)
	print(reduce(sum((1 for z in result.keys() if result[z] >= k)), n))


import sys

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	edges = [set() for i in range(n)]
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u) - 1, int(v) - 1]
		edges[u].add(v)
		edges[v].add(u)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	lut = set()
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u) - 1, int(v) - 1]
		lut.add((v, u))
	q = [0]
	covered = [0 for i in range(n)]
	tot_match = 0
	ind = 0
	while ind < len(q):
		node = q[ind]
		covered[node] = 1
		for val in edges[node]:
			if covered[val] == 0:
				if (val, node) in lut:
					tot_match += 1
				q.append(val)
		ind += 1
	covered = [0 for i in range(n)]
	tot_correct = 0
	q = [(-1, 0, tot_match)]
	ind = 0
	while ind < len(q):
		(fromn, node, tot_match) = q[ind]
		covered[node] = 1
		modif = 0
		if fromn != -1:
			if (fromn, node) in lut:
				modif += 1
			if (node, fromn) in lut:
				modif -= 1
		tot_match += modif
		for val in edges[node]:
			if covered[val] == 0:
				q.append((node, val, tot_match))
		if tot_match >= k:
			tot_correct += 1
		ind += 1
	divi = gcd(tot_correct, n)
	print(tot_correct // divi, end='')
	print('/', end='')
	print(n // divi)


from math import gcd
from collections import defaultdict

def is_win(parent, guesses, k):
	count = 0
	for (u, v) in guesses:
		if parent[v] == u:
			count += 1
	return count >= k

def dfs(root, adj):
	parent = {root: None}
	stack = [root]
	for i in adj:
		curr = stack.pop()
		for nei in adj[curr]:
			if nei != parent[curr]:
				parent[nei] = curr
				stack.append(nei)
	return parent

def walk_tree(root, parent, adj, num_correct, guesses, k):
	score = 0
	if num_correct >= k:
		score += 1
	stack = list(adj[root])
	undo_swap = dict()
	while len(stack):
		curr = stack.pop()
		if curr in undo_swap:
			(old_parent, num_correct) = undo_swap[curr]
			(parent[curr], parent[old_parent]) = (old_parent, None)
			continue
		old_parent = parent[curr]
		(parent[curr], parent[old_parent]) = (None, curr)
		undo_swap[curr] = (old_parent, num_correct)
		if (old_parent, curr) in guesses:
			num_correct -= guesses[old_parent, curr]
		if (curr, old_parent) in guesses:
			num_correct += guesses[curr, old_parent]
		if num_correct >= k:
			score += 1
		stack.append(curr)
		for nei in adj[curr]:
			if nei == old_parent:
				continue
			stack.append(nei)
	return score
q = int(input())
for _ in range(q):
	n = int(input())
	adj = {x: list() for x in range(1, n + 1)}
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	(g, k) = map(int, input().split())
	guesses = defaultdict(int)
	for _ in range(g):
		(u, v) = map(int, input().split())
		guesses[u, v] += 1
	parent = dfs(1, adj)
	num_correct = 0
	for (u, v) in guesses:
		if parent[v] == u:
			num_correct += guesses[u, v]
	count_win = walk_tree(1, parent, adj, num_correct, guesses, k)
	d = gcd(count_win, n)
	(num, denom) = (count_win // d, n // d)
	if num == 0:
		denom = 1
	print('{}/{}'.format(num, denom))


import sys

class NodeDesc:

	def __init__(self):
		self.ajdacencies = set()
		self.descendants = -1
		self.offset = 0

class Adjacency:

	def __init__(self, n):
		self.nodeID = n
		self.isV = False

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

class Graph:

	def __init__(self, num_nodes):
		self.num_nodes = num_nodes
		self.graph = [NodeDesc() for x in range(0, num_nodes)]
		self.threshold = 0
		self.guessRight = 0
		self.guessWrong = 0

	def addEdge(self, node1, node2, bidirectional=True):
		self.graph[node1].ajdacencies.add(Adjacency(node2))
		if bidirectional:
			self.graph[node2].ajdacencies.add(Adjacency(node1))

	def setupGame(self, edgeList, threshold):
		self.threshold = threshold
		for (u, v) in edgeList:
			for adj in self.graph[u].ajdacencies:
				adj.isV = adj.isV or adj.nodeID == v

	def DepthFirstSearch(self, min_node, max_node):
		self.guessRight = 0
		self.guessWrong = 0
		num_nodes = max_node - min_node + 1
		visited = [False] * (num_nodes + min_node)
		search_orders = []
		successes = 0
		trials = 0
		for i in range(min_node, len(visited)):
			if i == min_node:
				self.guessRight = 0
				self.guessWrong = 0
				visited = [False] * (num_nodes + min_node)
				search_order = []
				self.DepthFirstSearchRec(i, -1, visited, search_order)
				search_orders.append(search_order)
				successes += 1 if self.guessRight >= self.threshold else 0
			else:
				successes += 1 if self.guessRight + self.graph[i].offset >= self.threshold else 0
			trials += 1
		g = gcd(successes, trials)
		print('{}/{}'.format(successes // g, trials // g))
		return search_orders

	def DepthFirstSearchRec(self, node, parentID, visited, search_order):
		visited[node] = True
		search_order.append(node)
		Descendants = 1
		for adj in self.graph[node].ajdacencies:
			if adj.nodeID == parentID and adj.isV:
				self.graph[node].offset += 1
		for adj in self.graph[node].ajdacencies:
			if not visited[adj.nodeID]:
				self.graph[adj.nodeID].offset = self.graph[node].offset
				if adj.isV:
					self.guessRight += 1
					self.graph[adj.nodeID].offset -= 1
				d = self.DepthFirstSearchRec(adj.nodeID, node, visited, search_order)
				Descendants += d
			elif adj.isV:
				self.guessWrong += 1
		self.graph[node].descendants = Descendants
		return Descendants
lines = '2\n4\n1 2\n1 3\n3 4\n2 2\n1 2\n3 4\n3\n1 2\n1 3\n2 2\n1 2\n1 3\n'
aLines = [i for i in lines.split('\n') if len(i.strip()) > 0]
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	graph = Graph(n + 1)
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		graph.addEdge(u, v)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	edges = []
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		edges.append((u, v))
	graph.setupGame(edges, k)
	graphNodes = graph.DepthFirstSearch(1, n)


import os
import sys
adj = []
p = []

def dfs(v, par):
	ret = 0
	for u in p[v]:
		ret += +1 if par == u else 0
	for u in adj[v]:
		if u != par:
			ret += dfs(u, v)
	return ret

def dfs2(v, par, cur, lim):
	if par != -1:
		for u in p[par]:
			if u == v:
				cur += 1
	for u in p[v]:
		if u == par:
			cur -= 1
	ret = cur >= lim
	for u in adj[v]:
		if u != par:
			ret += dfs2(u, v, cur, lim)
	return ret

def gcd(a, b):
	return gcd(b % a, a) if a > 0 else b
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	adj = [[] for _ in range(n)]
	p = [[] for _ in range(n)]
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		u -= 1
		v -= 1
		p[v].append(u)
	cur = dfs(0, -1)
	ans = dfs2(0, -1, cur, k)
	d = gcd(ans, n)
	ans = ans // d
	n = n // d
	print('%d/%d' % (ans, n))


import os
import sys
from collections import defaultdict
from fractions import gcd

def storyOfATree(n, graph, k, guesses):
	memo = {}

	def recursive(v, w):
		if (v, w) not in memo:
			result = 1 if (v, w) in guesses else 0
			for i in graph[w]:
				if not i == v:
					result += recursive(w, i)
			memo[v, w] = result
		return memo[v, w]
	won = 0
	for i in graph.keys():
		total = 0
		for j in graph[i]:
			total += recursive(i, j)
		won += 1 if total >= k else 0
	x = gcd(won, n)
	print(won // x, '/', n // x, sep='')
q = int(input())
for q_itr in range(q):
	n = int(input())
	graph = defaultdict(set)
	for _ in range(n - 1):
		(v, w) = input().split()
		graph[v].add(w)
		graph[w].add(v)
	(g, k) = input().split()
	(g, k) = (int(g), int(k))
	guesses = set()
	for _ in range(g):
		guesses.add(tuple(input().split()))
	storyOfATree(n, graph, k, guesses)


from math import gcd
q = int(input())
for Q in range(q):
	n = int(input())
	edges = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		edges[u].append(v)
		edges[v].append(u)
	(g, k) = map(int, input().split())
	guesses = [set() for i in range(n + 1)]
	for i in range(g):
		(u, v) = map(int, input().split())
		guesses[v].add(u)
	parent = [0] * (n + 1)
	parent[1] = -1
	active = [1]
	while active:
		i = active.pop()
		for j in edges[i]:
			if parent[j] == 0:
				parent[j] = i
				edges[j].remove(i)
				active.append(j)
	correct = 0
	for i in range(1, n + 1):
		if parent[i] in guesses[i]:
			correct += 1
	active = [1]
	seen = [0] * (n + 1)
	wins = 0
	while active:
		i = active[-1]
		s = seen[i]
		if s == 0:
			if parent[i] in guesses[i]:
				correct -= 1
			if correct >= k:
				wins += 1
		else:
			j = edges[i][s - 1]
			if j in guesses[i]:
				correct -= 1
		if s < len(edges[i]):
			j = edges[i][s]
			seen[i] = s + 1
			if j in guesses[i]:
				correct += 1
			active.append(j)
		else:
			active.pop()
			if parent[i] in guesses[i]:
				correct += 1
	g = gcd(wins, n)
	print('{}/{}'.format(wins // g, n // g))


from fractions import Fraction

def correct(u, adj, guess, vis):
	c = 0
	vis[u] = True
	for v in adj[u]:
		if vis[v]:
			continue
		if (u, v) in guess:
			c += 1
		c += correct(v, adj, guess, vis)
	return c

def dfs(u, adj, guess, corr):
	for v in adj[u]:
		if corr[v] is not False:
			continue
		corr[v] = corr[u]
		if (u, v) in guess:
			corr[v] -= 1
		if (v, u) in guess:
			corr[v] += 1
		dfs(v, adj, guess, corr)

def solve(adj, guess, k):
	n = len(adj)
	corr = [False] * n
	root = 0
	corr[root] = correct(root, adj, guess, [False] * n)
	dfs(root, adj, guess, corr)
	wins = sum((c >= k for c in corr))
	return Fraction(wins, n)
q = int(input())
for _ in range(q):
	n = int(input())
	adj = [list() for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	guess = set()
	(g, k) = map(int, input().split())
	for _ in range(g):
		(u, v) = map(int, input().split())
		guess.add((u - 1, v - 1))
	if g < k:
		print('0/1')
	else:
		res = solve(adj, guess, k)
		print('0/1' if res == 0 else '1/1' if res == 1 else res)


from collections import defaultdict

def gcd(a, b):
	if b > a:
		(a, b) = (b, a)
	while b != 0:
		(a, b) = (b, a % b)
	return a

def dfs_with_backtracking(edges):
	node = 0
	stack = [(0, child) for child in edges[0]]
	visited = set([node])
	while stack:
		(parent, child) = stack[-1]
		if child in visited:
			yield (child, parent)
			stack.pop()
			continue
		yield (parent, child)
		visited.add(child)
		if len(visited) == len(edges):
			return
		for node in edges[child]:
			if node != parent:
				stack.append((child, node))

def modify(parent_array, n_correct, guess_dict, old_root, new_root):
	parent_array[old_root] = new_root
	parent_array[new_root] = None
	if new_root in guess_dict[old_root]:
		n_correct += 1
	if old_root in guess_dict[new_root]:
		n_correct -= 1
	return n_correct

def n_correct(edges, guesses):
	guess_dict = defaultdict(set)
	for (parent, child) in guesses:
		guess_dict[child].add(parent)
	parent_array = [None] * len(edges)
	root = 0
	stack = [root]
	while stack:
		node = stack.pop()
		for child in edges[node]:
			if child != parent_array[node]:
				parent_array[child] = node
				stack.append(child)
	n_correct = sum((1 for (parent, child) in guesses if parent_array[child] == parent))
	yield n_correct
	visited = set([root])
	for (parent, child) in dfs_with_backtracking(edges):
		n_correct = modify(parent_array, n_correct, guess_dict, parent, child)
		if child not in visited:
			visited.add(child)
			yield n_correct
q = int(input())
for _ in range(q):
	n = int(input())
	edges = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = (int(x) - 1 for x in input().split())
		edges[u].append(v)
		edges[v].append(u)
	(g, k) = (int(x) for x in input().split())
	guesses = []
	for _ in range(g):
		guesses.append(tuple((int(x) - 1 for x in input().split())))
	n_winners = sum((1 for i in n_correct(edges, guesses) if i >= k))
	factor = gcd(n_winners, n)
	print('{}/{}'.format(n_winners // factor, n // factor))


from collections import defaultdict
from fractions import Fraction

class Graph:

	def __init__(self, n):
		self.n = n
		self.graph = defaultdict(list)
		self.count = 0
		self.num = 0

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

class Graph2:

	def __init__(self, n):
		self.n = n
		self.graph = defaultdict(list)

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

def udpateParent(graph, parent, u):
	visited = [False] * graph.n
	updateParentUtils(graph, visited, parent, u)

def updateParentUtils(graph, visited, parent, u):
	visited[u] = True
	for v in graph.graph[u]:
		if visited[v] is False:
			parent[v] = u
			updateParentUtils(graph, visited, parent, v)

def getCount(graph, parent, graph2, u, k):
	visited = [False] * graph.n
	getCountUtils(graph, parent, graph2, visited, u, k)

def getCountUtils(graph, parent, graph2, visited, u, k):
	visited[u] = True
	if u == 0:
		for x in range(graph2.n):
			for v in graph2.graph[x]:
				if parent[v] == x:
					graph.num = graph.num + 1
	if graph.num >= k:
		graph.count = graph.count + 1
	for v in graph.graph[u]:
		if visited[v] is False:
			parent[v] = -1
			parent[u] = v
			s = 0
			num = graph.num
			for x in graph2.graph[u]:
				if x == v:
					graph.num -= 1
					s = s + 1
			for x in graph2.graph[v]:
				if x == u:
					graph.num = graph.num + 1
					s = s - 1
			getCountUtils(graph, parent, graph2, visited, v, k)
			parent[u] = -1
			parent[v] = u
			graph.num = num
q = int(input())
number = 0
for i in range(q):
	n = int(input())
	graph = Graph(n)
	graph2 = Graph2(n)
	for i in range(n - 1):
		(u, v) = list(map(int, input().split()))
		graph.addEdge(u - 1, v - 1)
	parent = [-1] * graph.n
	udpateParent(graph, parent, 0)
	(g, k) = list(map(int, input().split()))
	for i in range(g):
		(x, y) = list(map(int, input().split()))
		graph2.addEdge(x - 1, y - 1)
	getCount(graph, parent, graph2, 0, k)
	x = graph.count / graph.n
	if x == 0:
		print('0/1')
	elif x == 1:
		print('1/1')
	else:
		print(Fraction(graph.count, graph.n))


import sys

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def reduce_frac(n, d):
	fact = gcd(n, d)
	return (n // fact, d // fact)
verbose = False

def pr(*args):
	if verbose:
		print(*args, file=sys.stderr)

def solve(n, iedges, k, guesses):
	edges = [set() for _ in range(n + 1)]
	for (u, v) in iedges:
		edges[u].add(v)
		edges[v].add(u)
	guesses = set((tuple(g) for g in guesses))
	fg = [g for g in guesses if g[0] in edges[g[1]]]
	start = 1
	num_right = 0
	visited = (n + 1) * [False]
	queue = [start]
	while queue:
		nqueue = []
		for u in queue:
			visited[u] = True
			for v in edges[u]:
				if visited[v]:
					continue
				if (u, v) in guesses:
					num_right += 1
				nqueue.append(v)
		queue = nqueue
	results = (n + 1) * [False]

	def switch_root(p, u, prev_right):
		results[u] = prev_right >= k
		for v in edges[u]:
			if v == p:
				continue
			new_nr = prev_right
			if (u, v) in guesses:
				new_nr -= 1
			if (v, u) in guesses:
				new_nr += 1
			switch_root(u, v, new_nr)
	switch_root(0, start, num_right)
	return '%d/%d' % reduce_frac(sum((1 for res in results if res)), n)
import sys
readline = sys.stdin.readline
for _ in range(int(readline())):
	n = int(readline())
	edges = [[int(s) for s in readline().split()] for _ in range(n - 1)]
	(g, k) = [int(s) for s in readline().split()]
	guesses = [[int(s) for s in readline().split()] for _ in range(g)]
	print(solve(n, edges, k, guesses))


from fractions import Fraction

def firstDFS(p, u, G, guesses):
	score = 0
	for v in G[u]:
		if v != p:
			if (u, v) in guesses:
				score += 1
			score += firstDFS(u, v, G, guesses)
	return score

def secondDFS(p, u, G, guesses, score, k):
	win = int(score >= k)
	for v in G[u]:
		if v != p:
			newScore = score
			if (v, u) in guesses:
				newScore += 1
			if (u, v) in guesses:
				newScore -= 1
			win += secondDFS(u, v, G, guesses, newScore, k)
	return win

def probability(G, guesses, k, n):
	score = firstDFS(0, 1, G, guesses)
	won = secondDFS(0, 1, G, guesses, score, k)
	return Fraction(won, n)
for _ in range(int(input())):
	n = int(input())
	G = [[] for _ in range(n + 1)]
	for __ in range(n - 1):
		(u, v) = list(map(int, input().split()))
		G[u].append(v)
		G[v].append(u)
	(g, k) = list(map(int, input().split()))
	guesses = set([])
	for __ in range(g):
		guesses.add(tuple(map(int, input().split())))
	res = probability(G, guesses, k, n)
	print('%d/%d' % (res.numerator, res.denominator))


import math

class Queue:
	arr = []
	index = 0

	def get(self):
		if self.index >= len(self.arr):
			return None
		return self.arr[self.index]

	def add(self, value):
		self.arr.append(value)

	def pop(self):
		if self.get() == None:
			print('Bad')
			return
		value = self.arr[self.index]
		self.arr[self.index] = None
		self.index += 1
		return value

def result():
	res = 0
	n = len(edges) + 1
	adj = [[] for x in range(n + 1)]
	for edge in edges:
		adj[edge[0]].append(edge[1])
		adj[edge[1]].append(edge[0])
	scores = [0 for x in range(n)]
	visited = [False for x in range(n)]

	def DFS(index, visited, count, scores):
		total = 0
		visited[index] = True
		scores[index] += count
		prev = count
		for i in adj[index]:
			count = prev
			if visited[i] == True:
				continue
			if guesses.get((i, index), False):
				count += 1
			if guesses.get((index, i), False):
				total += 1
				count -= 1
			total += DFS(i, visited, count, scores)
		return total
	total = DFS(0, visited, 0, scores)
	for i in range(n):
		scores[i] += total
	for i in scores:
		if i >= k:
			res += 1
	return res
q = int(input())
for i in range(q):
	n = int(input())
	edges = []
	for j in range(n - 1):
		edges.append(list(map(int, input().rstrip().split())))
		edges[-1][0] -= 1
		edges[-1][1] -= 1
	guesses = {}
	(g, k) = map(int, input().rstrip().split())
	for i in range(g):
		guess = list(map(int, input().split()))
		guesses[guess[0] - 1, guess[1] - 1] = True
	res = result()
	if res == 0:
		print('0/1')
	else:
		gcd = math.gcd(res, n)
		res = res // gcd
		n = n // gcd
		print(str(res) + '/' + str(n))


from math import gcd

def search(v, par):
	ret = 0
	for u in p[v]:
		ret += +1 if par == u else 0
	for u in edges[v]:
		if u != par:
			ret += search(u, v)
	return ret

def count(v, par, cur, lim):
	if par != -1:
		for u in p[par]:
			if u == v:
				cur += 1
	for u in p[v]:
		if u == par:
			cur -= 1
	ret = cur >= lim
	for u in edges[v]:
		if u != par:
			ret += count(u, v, cur, lim)
	return ret
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	edges = [[] for _ in range(n + 1)]
	p = [[] for _ in range(n + 1)]
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		edges[int(u)].append(int(v))
		edges[int(v)].append(int(u))
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		p[int(v)].append(int(u))
	match = search(1, -1)
	ans = count(1, -1, match, k)
	d = gcd(ans, n)
	print(str(ans // d) + '/' + str(n // d))


def gcd(a, b):
	if not b:
		return a
	return gcd(b, a % b)

def dfs1(m, guess, root, seen):
	count = 0
	stack = []
	stack.append(root)
	seen.add(root)
	while len(stack):
		root = stack.pop(len(stack) - 1)
		for i in m[root]:
			if i not in seen:
				seen.add(i)
				count += 1 if root in guess and i in guess[root] else 0
				stack.append(i)
	return count

def dfs2(m, guess, root, seen, cost, k):
	stack = []
	stack.append((root, cost))
	seen.add(root)
	t_win = 0
	while len(stack):
		(root, cost) = stack.pop(len(stack) - 1)
		t_win += cost >= k
		for i in m[root]:
			if i not in seen:
				seen.add(i)
				stack.append((i, cost - (1 if root in guess and i in guess[root] else 0) + (1 if i in guess and root in guess[i] else 0)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	m = {}
	guess = {}
	seen = set()
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		if u not in m:
			m[u] = []
		m[u].append(v)
		if v not in m:
			m[v] = []
		m[v].append(u)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		if u not in guess:
			guess[u] = []
		guess[u].append(v)
	cost = dfs1(m, guess, 1, seen)
	seen = set()
	win = dfs2(m, guess, 1, seen, cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import math

def traversal(tree, node):
	ce = tree[node]
	for n in ce[1:]:
		if tree[node][0][0] == n:
			continue
		tree[n][0][0] = node
		traversal(tree, n)

def propagate(tree, node, v):
	ce = tree[node]
	for n in ce[1:]:
		if tree[node][0][0] == n:
			continue
		tree[n][0][1] += v
		propagate(tree, n, tree[n][0][1])

def buildall(root, tree, guesses, k):
	traversal(tree, root)
	reverse = []
	c = 0
	for g in guesses:
		if tree[g[1]][0][0] == g[0]:
			tree[root][0][1] += 1
			tree[g[1]][0][1] -= 1
		else:
			tree[g[0]][0][1] += 1
	propagate(tree, root, tree[root][0][1])
	score = 0
	for ne in tree[1:]:
		if ne[0][1] >= k:
			score += 1
	return score

def simplify(n, guesses):
	div = math.gcd(n, guesses)
	return (guesses // div, n // div)

def storyOfATree(n, tree, k, guesses):
	p = 0
	q = 1
	if len(guesses) >= k and k <= n - 1:
		p = buildall(1, tree, guesses, k)
		(p, q) = simplify(n, p)
	res = str(p) + '/' + str(q)
	return res
q = int(input())
for q_itr in range(q):
	n = int(input())
	tree = [[[0, 0]] for i in range(0, n + 1)]
	for _ in range(n - 1):
		edge = list(map(int, input().rstrip().split()))
		tree[edge[0]].append(edge[1])
		tree[edge[1]].append(edge[0])
	gk = input().split()
	g = int(gk[0])
	k = int(gk[1])
	guesses = []
	for _ in range(g):
		guesses.append(list(map(int, input().rstrip().split())))
	result = storyOfATree(n, tree, k, guesses)
	print(result)


import sys
from collections import defaultdict
from math import gcd

def dfs1():
	seen = {1}
	stack = [1]
	count = 0
	while stack:
		node = stack.pop()
		for child in tree[node]:
			if child not in seen:
				seen.add(child)
				count += (node, child) in guess
				stack.append(child)
	return count

def dfs2(cost, k):
	seen = {1}
	stack = [(1, cost)]
	t_win = 0
	while stack:
		(node, cost) = stack.pop()
		t_win += cost >= k
		for child in tree[node]:
			if child not in seen:
				seen.add(child)
				stack.append((child, cost - ((node, child) in guess) + ((child, node) in guess)))
	return t_win
t = int(input())
for _ in range(t):
	n = int(input())
	tree = defaultdict(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().split())
	guess = {tuple(map(int, input().split())) for i in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{}/{}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


def fraction(a, b):
	h = 1
	for i in range(a, 1, -1):
		if a % i == 0 and b % i == 0:
			h = i
			break
	a = str(a // h)
	b = str(b // h)
	s = a + '/' + b
	return s

def count_correct_guess(G, guess, root, n, k):
	parent = {root: None}
	visited1 = {root}
	stack1 = [root]
	while stack1:
		u = stack1.pop(0)
		for v in G[u]:
			if v not in visited1:
				visited1.add(v)
				parent[v] = u
				stack1.append(v)
	score = 0
	for e in guess:
		if parent[e[1]] == e[0]:
			score += 1
	scores = {root: score}
	visited = {root}
	stack = [root]
	while stack:
		u = stack.pop(0)
		for v in G[u]:
			if v not in visited:
				visited.add(v)
				stack.append(v)
				scores[v] = scores[u]
				if (v, u) in guess:
					scores[v] += 1
				if (u, v) in guess:
					scores[v] -= 1
	wins = 0
	for r in range(1, n + 1):
		if scores[r] >= k:
			wins += 1
	return wins
for _ in range(int(input())):
	n = int(input())
	G = {}
	for i in range(n - 1):
		(u, v) = (int(i) for i in input().split())
		if u in G:
			G[u].add(v)
		else:
			G[u] = {v}
		if v in G:
			G[v].add(u)
		else:
			G[v] = {u}
	(g, k) = (int(i) for i in input().split())
	guess = set()
	for _ in range(g):
		guess.add(tuple((int(i) for i in input().split())))
	wins = count_correct_guess(G, guess, 1, n, k)
	if wins == 0:
		print('0/1')
	elif wins == n:
		print('1/1')
	else:
		print(fraction(wins, n))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))


import sys
import queue
import math

class Graph:

	def __init__(self, n):
		self.edge_list = dict()
		for i in range(1, n + 1):
			self.edge_list[i] = set()
		self.score = dict()

	def add_edge(self, u, v):
		self.edge_list[u].add(v)
		self.edge_list[v].add(u)

	def nbrs(self, u):
		return self.edge_list[u]

	def compute_score(self, root, guesses):
		start = 1
		q = queue.Queue()
		q.put(1)
		closed = set()
		self.score[root] = 0
		while not q.empty():
			node = q.get()
			closed.add(node)
			for nbr in self.nbrs(node):
				if nbr in closed:
					continue
				q.put(nbr)
				if (node, nbr) in guesses.keys():
					self.score[root] += guesses[node, nbr]

	def compute_scores(self, root, guesses):
		start = 1
		q = queue.Queue()
		q.put(1)
		closed = set()
		while not q.empty():
			node = q.get()
			closed.add(node)
			for nbr in self.nbrs(node):
				if nbr in closed:
					continue
				q.put(nbr)
				temp = self.score[node]
				if (node, nbr) in guesses.keys():
					temp -= guesses[node, nbr]
				if (nbr, node) in guesses.keys():
					temp += guesses[nbr, node]
				self.score[nbr] = temp

	def count_scores(self, k):
		return sum([x >= k for x in self.score.values()])
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	G = Graph(n)
	for a1 in range(n - 1):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		G.add_edge(u, v)
	(g, k) = input().strip().split(' ')
	(g, k) = [int(g), int(k)]
	guesses = dict()
	for a1 in range(g):
		(u, v) = input().strip().split(' ')
		(u, v) = [int(u), int(v)]
		if (u, v) not in guesses:
			guesses[u, v] = 0
		guesses[u, v] += 1
	G.compute_score(1, guesses)
	G.compute_scores(1, guesses)
	count = G.count_scores(k)
	if count == 0:
		print('%d/%d' % (0, 1))
	else:
		temp = math.gcd(count, n)
		count //= temp
		n //= temp
		print('%d/%d' % (count, n))


import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10 ** 9)

def dfs1():
	root = 1
	seen = {root}
	stack = [root]
	count = 0
	while stack:
		root = stack.pop()
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				count += (root, node) in guess
				stack.append(node)
	return count

def dfs2(cost, k):
	root = 1
	seen = {root}
	stack = [(root, cost)]
	t_win = 0
	while stack:
		(root, cost) = stack.pop()
		t_win += cost >= k
		for node in tree[root]:
			if node not in seen:
				seen.add(node)
				stack.append((node, cost - ((root, node) in guess) + ((node, root) in guess)))
	return t_win
q = int(input().strip())
for a0 in range(q):
	n = int(input().strip())
	tree = defaultdict(list)
	for a1 in range(n - 1):
		(u, v) = map(int, input().strip().split(' '))
		tree[u].append(v)
		tree[v].append(u)
	(g, k) = map(int, input().strip().split(' '))
	guess = {tuple(map(int, input().split())) for _ in range(g)}
	cost = dfs1()
	win = dfs2(cost, k)
	g = gcd(win, n)
	print('{0}/{1}'.format(win // g, n // g))