There is an undirected tree of $n$ vertices, connected by $n-1$ bidirectional edges. There is also a snake stuck inside of this tree. Its head is at vertex $a$ and its tail is at vertex $b$. The snake's body occupies all vertices on the unique simple path between $a$ and $b$.

The snake wants to know if it can reverse itself  — that is, to move its head to where its tail started, and its tail to where its head started. Unfortunately, the snake's movements are restricted to the tree's structure.

In an operation, the snake can move its head to an adjacent vertex not currently occupied by the snake. When it does this, the tail moves one vertex closer to the head, so that the length of the snake remains unchanged. Similarly, the snake can also move its tail to an adjacent vertex not currently occupied by the snake. When it does this, the head moves one unit closer to the tail. [Image] Let's denote a snake position by $(h,t)$, where $h$ is the index of the vertex with the snake's head, $t$ is the index of the vertex with the snake's tail. This snake can reverse itself with the movements $(4,7)\to (5,1)\to (4,2)\to (1, 3)\to (7,2)\to (8,1)\to (7,4)$. 

Determine if it is possible to reverse the snake with some sequence of operations.


-----Input-----

The first line contains a single integer $t$ ($1\le t\le 100$)  — the number of test cases. The next lines contain descriptions of test cases.

The first line of each test case contains three integers $n,a,b$ ($2\le n\le 10^5,1\le a,b\le n,a\ne b$).

Each of the next $n-1$ lines contains two integers $u_i,v_i$ ($1\le u_i,v_i\le n,u_i\ne v_i$), indicating an edge between vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.


-----Output-----

For each test case, output "YES" if it is possible for the snake to reverse itself, or "NO" otherwise.


-----Example-----
Input
4
8 4 7
1 2
2 3
1 4
4 5
4 6
1 7
7 8
4 3 2
4 3
1 2
2 3
9 3 5
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
16 15 12
1 2
2 3
1 4
4 5
5 6
6 7
4 8
8 9
8 10
10 11
11 12
11 13
13 14
10 15
15 16

Output
YES
NO
NO
YES



-----Note-----

The first test case is pictured above.

In the second test case, the tree is a path. We can show that the snake cannot reverse itself.

In the third test case, we can show that the snake cannot reverse itself.

In the fourth test case, an example solution is:

$(15,12)\to (16,11)\to (15,13)\to (10,14)\to (8,13)\to (4,11)\to (1,10)$

$\to (2,8)\to (3,4)\to (2,5)\to (1,6)\to (4,7)\to (8,6)\to (10,5)$

$\to (11,4)\to (13,8)\to (14,10)\to (13,15)\to (11,16)\to (12,15)$.

Difficulty: HARD

Starter code:

Solutions:
import sys
T = int(sys.stdin.readline().strip())
while T > 0:
	T -= 1
	(n, st, en) = sys.stdin.readline().strip().split(' ')
	n = int(n)
	st = int(st)
	en = int(en)
	d = [[0, 0, 0]]
	height = [0]
	e = {}
	flag = []
	maxson = [-1]
	target_list = []
	for i in range(1, n):
		(x, y) = sys.stdin.readline().strip().split(' ')
		x = int(x)
		y = int(y)
		maxson.append(-1)
		d.append([0, 0, 0])
		height.append(0)
		e[x] = e.get(x, []) + [y]
		e[y] = e.get(y, []) + [x]
	d.append([0, 0, 0])
	height.append(0)
	maxson.append(-1)
	stack_queue = []
	stack_queue.append((st, 0, -1, 0, 0))
	while len(stack_queue) > 0:
		now = stack_queue.pop()
		(x, h, fa, r, idone) = now
		if r == 0:
			for i1 in range(idone, len(e[x])):
				i = e[x][i1]
				if fa == i:
					continue
				if i == en:
					flag.append(i)
				stack_queue.append((x, h, fa, 1, i1))
				stack_queue.append((i, h + 1, x, 0, 0))
				break
			continue
		if r == 1:
			i = e[x][idone]
			if len(flag) > 0 and i == flag[-1]:
				flag.append(x)
			else:
				height[x] = max(height[x], height[i] + 1)
			di = d[i][0] + 1
			for ss in range(3):
				if d[x][ss] > di:
					continue
				if ss == 0:
					maxson[x] = i
				(d[x][ss], di) = (di, d[x][ss])
			stack_queue.append((x, h, fa, 0, idone + 1))
	stack_queue = []
	stack_queue.append((st, -1))
	while len(stack_queue) > 0:
		now = stack_queue.pop()
		(x, fa) = now
		if d[x][-1] + 1 >= len(flag):
			target_list.append(x)
		for i in e[x]:
			if fa == i:
				continue
			if i == maxson[x]:
				upx = d[x][1] + 1
			else:
				upx = d[x][0] + 1
			for ss in range(3):
				if d[i][ss] > upx:
					continue
				(d[i][ss], upx) = (upx, d[i][ss])
			stack_queue.append((i, x))
	if not len(target_list) > 0:
		print('NO')
		continue
	ll = len(flag)
	head_l = []
	tail_l = []
	for i in range(ll):
		if len(head_l) > 0:
			if head_l[-1] < height[flag[i]] - i:
				head_l.append(height[flag[i]] - i)
			else:
				head_l.append(head_l[-1])
		else:
			head_l.append(height[flag[i]] - i)
		if len(tail_l) > 0:
			if tail_l[-1] < height[flag[ll - 1 - i]] - i:
				tail_l.append(height[flag[ll - 1 - i]] - i)
			else:
				tail_l.append(tail_l[-1])
		else:
			tail_l.append(height[flag[ll - 1 - i]] - i)
	tail_l = tail_l[::-1]
	l = 0
	r = ll - 1
	while l < r:
		if l < tail_l[r]:
			l = tail_l[r]
		elif r > ll - 1 - head_l[l]:
			r = ll - 1 - head_l[l]
		else:
			break
	if l >= r:
		print('YES')
	else:
		print('NO')


class Solution:

	def __init__(self):
		self.his = set()
		self.dp = {}
		self.get_input()

	def get_input(self):
		(self.n, head, tail) = [int(tmp) for tmp in input().strip().split(' ')]
		head -= 1
		tail -= 1
		self.graph = [[] for _ in range(self.n)]
		for _ in range(self.n - 1):
			(x, y) = [int(tmp) - 1 for tmp in input().strip().split(' ')]
			self.graph[x].append(y)
			self.graph[y].append(x)
		pre = [-1] * self.n
		length = [-1] * self.n
		length[head] = 1
		lst_a = [head]
		lst_b = []
		while length[tail] < 0:
			for x in lst_a:
				for y in self.graph[x]:
					if length[y] >= 0:
						continue
					pre[y] = x
					length[y] = length[x] + 1
					lst_b.append(y)
			lst_a = lst_b
			lst_b = []
		self.snake = [tail]
		while self.snake[-1] != head:
			self.snake.append(pre[self.snake[-1]])

	def get_path(self):
		(self.path, self.sec) = self.get_path_rec(self.snake[1], self.snake[0])

	def get_path_rec(self, a, b):
		oa = a
		ob = b
		if (a, b) in self.dp:
			return self.dp[a, b]
		pre_path = [b]
		while len(self.graph[b]) == 2:
			tmp = b
			b = self.graph[b][0] if self.graph[b][0] != a else self.graph[b][1]
			a = tmp
			pre_path = [b] + pre_path
		if len(self.graph[b]) == 1:
			self.dp[oa, ob] = (pre_path, 0)
			return (pre_path, 0)
		path_list = []
		sec_list = []
		for x in self.graph[b]:
			if x == a:
				continue
			(path, sec) = self.get_path_rec(b, x)
			path_list.append(path)
			sec_list.append(sec)
		path_list.sort(key=lambda x: -len(x))
		self.dp[oa, ob] = (path_list[0] + pre_path, max(len(path_list[1]) + 1, max(sec_list)))
		return (path_list[0] + pre_path, max(len(path_list[1]) + 1, max(sec_list)))

	def move(self):
		length = len(self.snake)
		self.snake = self.path[:-1] + self.snake
		self.snake = self.snake[:length]
		for i in range(int(len(self.snake) / 2)):
			(self.snake[i], self.snake[-i - 1]) = (self.snake[-i - 1], self.snake[i])

	def get_result(self):
		if len(self.snake) == 1:
			return 'YES'
		while (self.snake[1], self.snake[0]) not in self.his:
			self.his.add((self.snake[1], self.snake[0]))
			self.get_path()
			if self.sec >= len(self.snake):
				return 'YES'
			self.move()
		return 'NO'
t = int(input().strip())
for _ in range(t):
	s = Solution()
	print(s.get_result())


from sys import stdin
import itertools
input = stdin.readline

def getint():
	return int(input())

def getints():
	return list(map(int, input().split()))

def getint1():
	return list(map(lambda x: int(x) - 1, input().split()))

def getstr():
	return input()[:-1]

def solve():
	(n, a, b) = getint1()
	n += 1
	adj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = getint1()
		adj[u].append(v)
		adj[v].append(u)
	max_child = [[-1] * 3 for _ in range(n)]
	stack = [(a, -1, 1)]
	while stack:
		(u, p, flag) = stack.pop()
		if p != -1 and len(adj[u]) < 2:
			max_child[u][0] = 1
			continue
		if flag == 1:
			stack.append((u, p, 0))
			for v in adj[u]:
				if v == p:
					continue
				stack.append((v, u, 1))
		else:
			for v in adj[u]:
				if v == p:
					continue
				len_v = max_child[v][0] + 1
				if len_v > max_child[u][0]:
					max_child[u][2] = max_child[u][1]
					max_child[u][1] = max_child[u][0]
					max_child[u][0] = len_v
				elif len_v > max_child[u][1]:
					max_child[u][2] = max_child[u][1]
					max_child[u][1] = len_v
				elif len_v > max_child[u][2]:
					max_child[u][2] = len_v
	body = []
	ret = [False] * n
	max_parent = [-1] * n
	stack.clear()
	stack = [(a, -1, 0)]
	while stack:
		(u, p, mxp) = stack.pop()
		if mxp >= 0:
			stack.append((u, p, -1))
			if p != -1 and len(adj[u]) < 2:
				continue
			max_parent[u] = mxp + 1
			chlen = [max_parent[u], -3]
			for v in adj[u]:
				if v == p:
					continue
				len_v = max_child[v][0] + 1
				if len_v > chlen[0]:
					chlen[1] = chlen[0]
					chlen[0] = len_v
				elif len_v > chlen[1]:
					chlen[1] = len_v
			for v in adj[u]:
				if v == p:
					continue
				stack.append((v, u, chlen[int(max_child[v][0] + 1 == chlen[0])]))
		else:
			is_body = u == b
			if not is_body:
				for v in adj[u]:
					if v != p and ret[v]:
						is_body = True
						break
			if is_body:
				body.append(u)
			ret[u] = is_body
	del ret
	ok = False
	body_len = len(body)
	can_turn = [False] * n
	for i in range(n):
		if 3 <= sum((1 for l in max_child[i] + [max_parent[i]] if l >= body_len)):
			can_turn[i] = True
			ok = True
	if not ok:
		print('NO')
		return
	treelen = [1] * body_len
	for i in range(body_len):
		cur = body[i]
		pre = -1 if i == 0 else body[i - 1]
		nxt = -1 if i + 1 == body_len else body[i + 1]
		for v in adj[cur]:
			if v == pre or v == nxt:
				continue
			treelen[i] = max(treelen[i], max_child[v][0] + 1)
			if can_turn[v]:
				can_turn[cur] = True
				continue
			stack = [(v, cur)]
			while stack and (not can_turn[cur]):
				(u, p) = stack.pop()
				for w in adj[u]:
					if w == p:
						continue
					if can_turn[w]:
						can_turn[cur] = True
						break
					stack.append((w, u))
			stack.clear()
	l = 0
	r = body_len - 1
	lmax = treelen[r] - 1
	rmin = body_len - treelen[l]
	ok = can_turn[body[l]] or can_turn[body[r]]
	while not ok and (l < lmax or rmin < r):
		if l < lmax:
			l += 1
			rmin = min(rmin, l + (body_len - treelen[l]))
		if rmin < r:
			r -= 1
			lmax = max(lmax, r - (body_len - treelen[r]))
		if can_turn[body[l]] or can_turn[body[r]]:
			ok = True
	print('YES' if ok else 'NO')
	return
for _ in range(getint()):
	solve()


import sys
from collections import deque
t = int(input())
for _ in range(t):
	(n, a, b) = [int(x) for x in input().split()]
	a -= 1
	b -= 1
	edges = set()
	adj = [[] for x in range(n)]
	for _ in range(n - 1):
		(u, v) = [int(x) for x in sys.stdin.readline().split()]
		u -= 1
		v -= 1
		edges.add((u, v))
		edges.add((v, u))
		adj[u].append(v)
		adj[v].append(u)
	to_a = [-1 for x in range(n)]
	to_a[a] = a
	stack = [a]
	while len(stack):
		cur = stack.pop()
		for nb in adj[cur]:
			if to_a[nb] == -1:
				to_a[nb] = cur
				stack.append(nb)
	snake = [b]
	while snake[-1] != a:
		snake.append(to_a[snake[-1]])
	snake = deque(snake)
	adj = [set(l) for l in adj]
	leaves = [x for x in range(n) if len(adj[x]) == 1]
	num_branch_points = sum([1 for l in adj if len(l) >= 3])
	new_leaves = []
	if len(snake) == 2:
		print('YES' if num_branch_points >= 1 else 'NO')
		continue
	while True:
		head = snake.pop()
		tail = snake.popleft()
		if len(adj[head]) == 1 and len(adj[tail]) == 1:
			print('NO')
			break
		if len(adj[head]) != 1:
			snake.append(head)
		else:
			snake.appendleft(tail)
		for leaf in leaves:
			if len(adj[leaf]) == 0:
				continue
			nb = adj[leaf].pop()
			adj[nb].remove(leaf)
			if len(adj[nb]) == 2:
				num_branch_points -= 1
			if len(adj[nb]) == 1:
				new_leaves.append(nb)
		(leaves, new_leaves) = (new_leaves, [])
		if num_branch_points == 0:
			print('NO')
			break
		if len(snake) == 2:
			print('YES')
			break


import sys
import time
tstart = int(round(time.time() * 1000))
casecount = int(sys.stdin.readline())
debug = False
for icase in range(0, casecount):
	ss = sys.stdin.readline().strip().split(' ')
	n = int(ss[0])
	a = int(ss[1])
	b = int(ss[2])
	if a == b:
		print('YES')
		continue
	edges = [[] for i in range(0, n + 1)]
	edgecount = [0 for i in range(0, n + 1)]
	edge2info = {}
	for i in range(0, n - 1):
		ss2 = sys.stdin.readline().strip().split(' ')
		u = int(ss2[0])
		v = int(ss2[1])
		edges[u].append(v)
		edges[v].append(u)
		edge2info[tuple([u, v])] = 0
		edge2info[tuple([v, u])] = 0
		edgecount[u] += 1
		edgecount[v] += 1
	path = [0 for i in range(0, n + 1)]
	path[b] = -1
	vlist = [b]
	i = 0
	found = False
	while i < n and found == False:
		for j in edges[vlist[i]]:
			if path[j] == 0:
				path[j] = vlist[i]
				vlist.append(j)
				if j == a:
					found = True
					break
		i += 1
	startpath = [a]
	i = a
	while i != b:
		i = path[i]
		startpath.append(i)
	length = len(startpath)
	snakepoint = {}
	for i in startpath:
		snakepoint[i] = 1
	appendegdes = []
	visited = [0 for i in range(0, n + 1)]
	for (k, v) in edge2info.items():
		if edgecount[k[0]] == 1:
			appendegdes.append(k)
			edge2info[k] = 1
	i = 0
	while i < len(appendegdes):
		pa = appendegdes[i][0]
		pb = appendegdes[i][1]
		visited[pa] = 1
		edgecount[pb] -= 1
		if edgecount[pb] <= 1:
			currentcount = edge2info[appendegdes[i]]
			if currentcount >= length:
				break
			for pn in edges[pb]:
				if edgecount[pb] == 1 and visited[pn] == 0 or (edgecount[pb] == 0 and edgecount[pn] >= 1):
					edge2info[tuple([pb, pn])] = currentcount + 1
					appendegdes.append(tuple([pb, pn]))
					visited[pb] = 1
		i += 1
	vpoint = []
	pathcount = [0 for i in range(0, n + 1)]
	for (k, v) in edge2info.items():
		if v == 0:
			edge2info[k] = length
		if v + 1 >= length or v == 0:
			pathcount[k[1]] += 1
	for i in range(1, n + 1):
		if pathcount[i] >= 3:
			vpoint.append(i)
	if debug:
		print(n, length, startpath)
		print(vpoint)
	if len(vpoint) == 0:
		print('NO')
		continue
	status = False
	for x in vpoint[0:1]:
		if status == True:
			break
		if x == a or x == b:
			print('YES')
			status = True
			break
		pointset = {}
		pointset[x] = 1
		appendlist = [x]
		found = False
		nearpoint = 0
		if x in snakepoint:
			found = True
			nearpoint = x
		i = 0
		while i < len(appendlist) and found == False:
			for j in edges[appendlist[i]]:
				if j in snakepoint:
					found = True
					nearpoint = j
					break
				if j not in pointset:
					pointset[j] = 1
					appendlist.append(j)
			i += 1
		if debug:
			print(found, nearpoint, startpath.index(nearpoint))
		index = startpath.index(nearpoint)
		if index == 0 or index == length - 1:
			print('YES')
			status = True
			break
		if edge2info[tuple([startpath[index - 1], nearpoint])] + 1 < length and edge2info[tuple([startpath[index + 1], nearpoint])] + 1 < length:
			continue
		method = 0
		head = 0
		tail = length - 1
		nomovecount = 0
		prehead = head
		pretail = tail
		while nomovecount < 2:
			if method == 0:
				movecount = edge2info[tuple([startpath[head], startpath[head + 1]])] - 1
				tail = tail - movecount
				head = head - movecount
				if movecount == 0 or tail == pretail:
					nomovecount += 1
				pretail = tail
				if tail <= index:
					print('YES')
					status = True
					break
			else:
				movecount = edge2info[tuple([startpath[tail], startpath[tail - 1]])] - 1
				head = head + movecount
				tail = tail + movecount
				if movecount == 0 or head == prehead:
					nomovecount += 1
				prehead = head
				if head >= index:
					print('YES')
					status = True
					break
			method = 1 - method
		break
	if status == False:
		print('NO')