You are given a weighted tree with $n$ vertices. Recall that a tree is a connected graph without any cycles. A weighted tree is a tree in which each edge has a certain weight. The tree is undirected, it doesn't have a root.

Since trees bore you, you decided to challenge yourself and play a game on the given tree.

In a move, you can travel from a node to one of its neighbors (another node it has a direct edge with).

You start with a variable $x$ which is initially equal to $0$. When you pass through edge $i$, $x$ changes its value to $x ~\mathsf{XOR}~ w_i$ (where $w_i$ is the weight of the $i$-th edge).

Your task is to go from vertex $a$ to vertex $b$, but you are allowed to enter node $b$ if and only if after traveling to it, the value of $x$ will become $0$. In other words, you can travel to node $b$ only by using an edge $i$ such that $x ~\mathsf{XOR}~ w_i = 0$. Once you enter node $b$ the game ends and you win.

Additionally, you can teleport at most once at any point in time to any vertex except vertex $b$. You can teleport from any vertex, even from $a$.

Answer with "YES" if you can reach vertex $b$ from $a$, and "NO" otherwise.

Note that $\mathsf{XOR}$ represents the bitwise XOR operation .


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains three integers $n$, $a$, and $b$ ($2 \leq n \leq 10^5$), ($1 \leq a, b \leq n; a \ne b$) — the number of vertices, and the starting and desired ending node respectively.

Each of the next $n-1$ lines denotes an edge of the tree. Edge $i$ is denoted by three integers $u_i$, $v_i$ and $w_i$  — the labels of vertices it connects ($1 \leq u_i, v_i \leq n; u_i \ne v_i; 1 \leq w_i \leq 10^9$) and the weight of the respective edge.

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


-----Output-----

For each test case output "YES" if you can reach vertex $b$, and "NO" otherwise.


-----Examples-----

Input
3
5 1 4
1 3 1
2 3 2
4 3 3
3 5 1
2 1 2
1 2 2
6 2 3
1 2 1
2 3 1
3 4 1
4 5 3
5 6 5
Output
YES
NO
YES


-----Note-----

For the first test case, we can travel from node $1$ to node $3$, $x$ changing from $0$ to $1$, then we travel from node $3$ to node $2$, $x$ becoming equal to $3$. Now, we can teleport to node $3$ and travel from node $3$ to node $4$, reaching node $b$, since $x$ became equal to $0$ in the end, so we should answer "YES".

For the second test case, we have no moves, since we can't teleport to node $b$ and the only move we have is to travel to node $2$ which is impossible since $x$ wouldn't be equal to $0$ when reaching it, so we should answer "NO".

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Graph algorithms

Graph traversal


Solutions:
import sys
from sys import stdin
from collections import deque
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
input = sys.stdin.readline
stack = []
startset = set()
res = []
t = int(input())
for _ in range(t):
	(n, st, fi) = map(int, input().split())
	g = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b, w) = map(int, input().split())
		g[a].append((b, w))
		g[b].append((a, w))
	startset.clear()
	used = [False] * (n + 1)
	used[fi] = True
	stack.append((st, 0))
	while stack:
		(v, wei) = stack.pop()
		used[v] = True
		startset.add(wei)
		for (n_node, w) in g[v]:
			if not used[n_node]:
				stack.append((n_node, wei ^ w))
	used = [False] * (n + 1)
	stack.append((fi, 0))
	found = False
	while stack:
		(v, wei) = stack.pop()
		used[v] = True
		if v != fi and wei in startset:
			stack.clear()
			found = True
			break
		for (n_node, w) in g[v]:
			if not used[n_node]:
				stack.append((n_node, wei ^ w))
	res.append('YES' if found else 'NO')
print(*res, sep='\n')


t = int(input())
for _ in range(t):

	def sol():
		(n, a, b) = map(int, input().split())
		a -= 1
		b -= 1
		edges = [[] for i in range(n)]
		for i in range(n - 1):
			(v1, v2, w) = map(int, input().split())
			v1 -= 1
			v2 -= 1
			edges[v1].append((v2, w))
			edges[v2].append((v1, w))
		from_a = set([0])
		from_b = set()
		visited = [False for _ in range(n)]
		hack = [False]

		def dfs(vc, ccur, from_arr):
			stack = [(vc, ccur)]
			while stack:
				(v, cur) = stack.pop()
				visited[v] = True
				for (to, we) in edges[v]:
					if not visited[to] and to == b and (cur ^ we == 0):
						hack[0] = True
					if not visited[to] and to != b:
						from_arr.add(cur ^ we)
						stack.append((to, cur ^ we))
		dfs(a, 0, from_a)
		if hack[0]:
			return 'YES'
		visited = [False for _ in range(n)]
		dfs(b, 0, from_b)
		p = set(from_a).intersection(set(from_b))
		if p:
			return 'YES'
		else:
			return 'NO'
	print(sol())


stack = []
hashesSt = set()
t = int(input())
for _ in range(t):
	(n, st, fi) = map(int, input().split())
	st -= 1
	fi -= 1
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b, w) = map(int, input().split())
		a -= 1
		b -= 1
		g[a].append((b, w))
		g[b].append((a, w))
	hashesSt.clear()
	used = [False] * n
	used[fi] = True
	stack.append((st, 0))
	while stack:
		(ver, hsh) = stack.pop()
		used[ver] = True
		hashesSt.add(hsh)
		for (to, w) in g[ver]:
			if not used[to]:
				stack.append((to, hsh ^ w))
	used = [False] * n
	stack.append((fi, 0))
	found = False
	while stack:
		(ver, hsh) = stack.pop()
		used[ver] = True
		if ver != fi and hsh in hashesSt:
			stack.clear()
			found = True
			break
		for (to, w) in g[ver]:
			if not used[to]:
				stack.append((to, hsh ^ w))
	print('YES' if found else 'NO')


from collections import Counter
import sys, threading
input = lambda : sys.stdin.readline().strip()

def main():
	for _ in range(int(input())):
		(n, a, b) = map(int, input().split())
		adj = [[] for _ in range(n + 1)]
		for _ in range(n - 1):
			(u, v, w) = map(int, input().split())
			adj[u].append((v, w))
			adj[v].append((u, w))
		(ok, cnt) = (False, Counter())

		def dfs1(u, p, xor):
			cnt[xor] += 1
			for (v, w) in adj[u]:
				if v == p:
					continue
				dfs1(v, u, xor ^ w)
		for (v, w) in adj[b]:
			dfs1(v, b, w)

		def dfs2(u, p, xor):
			nonlocal ok
			if u == b:
				return
			if cnt[xor]:
				ok = True
				return
			for (v, w) in adj[u]:
				if v == p:
					continue
				dfs2(v, u, xor ^ w)
		dfs2(a, -1, 0)
		print('YES' if ok else 'NO')
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


t = int(input())

def dfs(graph, src, terminate=None):
	visited = set()
	xor = [-1 for i in range(len(graph))]
	xor[src] = 0
	stack = [src]
	visited.add(src)
	while stack:
		u = stack.pop()
		if u == terminate:
			continue
		for (v, w) in graph[u]:
			if v not in visited:
				if xor[v] ^ w == 0 or v != terminate:
					xor[v] = xor[u] ^ w
					visited.add(v)
					stack.append(v)
	return xor

def solve():
	(n, a, b) = map(int, input().split())
	adj = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		adj[u - 1].append((v - 1, w))
		adj[v - 1].append((u - 1, w))
	x1 = dfs(adj, a - 1, terminate=b - 1)
	x2 = dfs(adj, b - 1)
	aa = set()
	for (i, xx) in enumerate(x1):
		if i == b - 1 and xx == 0:
			print('YES')
			return
		else:
			aa.add(xx)
	bb = set()
	for (i, xx) in enumerate(x2):
		if i != b - 1:
			bb.add(xx)
	for x in aa:
		if x in bb and x != -1:
			print('YES')
			return
	print('NO')
for _ in range(t):
	solve()


def main():
	for _ in range(int(input())):
		(n, a, b) = map(int, input().split())
		a -= 1
		b -= 1
		graph = [[] for _ in range(n)]
		for _ in range(n - 1):
			(x, y, w) = map(int, input().split())
			x -= 1
			y -= 1
			graph[x].append((y, w))
			graph[y].append((x, w))
		xors = set()

		def dfs(node, parent, xor):
			if node == a and xor == 0:
				return True
			for (v, w) in graph[node]:
				if v == parent:
					continue
				if dfs(v, node, xor ^ w):
					return True
				xors.add(xor ^ w)
			return False
		if dfs(b, -1, 0):
			print('YES')
			continue

		def dfs(node, parent, xor):
			if node == b:
				return xor == 0
			if xor in xors:
				return True
			for (v, w) in graph[node]:
				if v == parent:
					continue
				if dfs(v, node, xor ^ w):
					return True
			return False
		path = [a]
		print('YES' if dfs(a, -1, 0) else 'NO')
import sys, threading
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(g, a, b):

	def bfs1(start):
		q = [(start, 0)]
		visited = {start}
		ans = set()
		while q:
			newQ = []
			for (u, x) in q:
				if u != b:
					ans.add(x)
				for v in g[u]:
					if v not in visited:
						newQ.append([v, x ^ g[u][v]])
						visited.add(v)
			q = newQ
		return ans
	target = bfs1(b)
	if 0 in target:
		return 'YES'
	q = [(a, 0)]
	visited = {a}
	while q:
		newQ = []
		for (u, x) in q:
			if x in target:
				return 'YES'
			for v in g[u]:
				if v != b and v not in visited:
					newQ.append([v, x ^ g[u][v]])
					visited.add(v)
		q = newQ
	return 'NO'
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	g = {i: collections.defaultdict(int) for i in range(n)}
	for _ in range(n - 1):
		(u, v, w) = map(int, input().split())
		g[u - 1][v - 1] = w
		g[v - 1][u - 1] = w
	print(solve(g, a - 1, b - 1))


testcase = int(input())
for _ in range(testcase):
	(n, a, b) = [int(num) for num in input().split()]
	graph = {i: set() for i in range(1, n + 1)}
	for _ in range(n - 1):
		(v0, v1, w) = [int(num) for num in input().split()]
		graph[v0].add((v1, w))
		graph[v1].add((v0, w))
	seen = set()
	seen.add(a)
	ha = [(a, 0)]
	ass = set()
	ass.add(0)
	while ha:
		(q, xor) = ha.pop()
		for (adj, w) in graph[q]:
			if adj not in seen:
				if adj == b:
					continue
				seen.add(adj)
				k = xor ^ w
				ha.append((adj, k))
				ass.add(k)
	seen = set()
	seen.add(b)
	hb = [(b, 0)]
	bss = set()
	while hb:
		(q, xor) = hb.pop()
		for (adj, w) in graph[q]:
			if adj not in seen:
				seen.add(adj)
				k = xor ^ w
				hb.append((adj, k))
				bss.add(k)
	bss = list(bss)
	bss = [num in ass for num in bss]
	print('YES' if any(bss) else 'NO')


from collections import defaultdict, deque
t = int(input())

def bfs(graph, x):
	q = deque([(x, 0)])
	v = {x}
	xor = {}
	while len(q) > 0:
		(curr, xorval) = q.pop()
		xor[curr] = xorval
		for (j, w) in graph[curr]:
			if j not in v:
				v.add(j)
				q.appendleft((j, xorval ^ w))
	return xor
for _ in range(t):
	(n, a, b) = map(int, input().split())
	graph = defaultdict(set)
	for _ in range(n - 1):
		(u, v, w) = map(int, input().split())
		graph[u].add((v, w))
		graph[v].add((u, w))
	xor = bfs(graph, b)
	bvals = set()
	for i in graph:
		if i != b:
			bvals.add(xor[i])
	pos = xor[a] == 0
	q = deque([(a, 0)])
	v = {a, b}
	while len(q) > 0:
		(curr, xorval) = q.pop()
		if xorval in bvals:
			pos = True
			break
		for (j, w) in graph[curr]:
			if j not in v:
				v.add(j)
				q.appendleft((j, xorval ^ w))
	print('YES' if pos else 'NO')


from bisect import bisect
from collections import deque
for tcase in range(int(input())):
	(n, a, b) = map(int, input().split())
	adj = [[] for u in range(n + 1)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		adj[u].append((v, w))
		adj[v].append((u, w))
	(xa, xb) = ([-1] * (n + 1), [-1] * (n + 1))
	q = deque()
	xb[b] = 0
	q.append(b)
	while len(q) > 0:
		u = q.popleft()
		for (v, w) in adj[u]:
			if xb[v] == -1:
				xb[v] = xb[u] ^ w
				q.append(v)
	q = deque()
	xa[a] = 0
	xa[b] = -2
	q.append(a)
	while len(q) > 0:
		u = q.popleft()
		for (v, w) in adj[u]:
			if xa[v] == -1:
				xa[v] = xa[u] ^ w
				q.append(v)
	s = [xb[u] for u in range(1, n + 1) if u != b]
	s.sort()
	ans = False
	for u in range(1, n + 1):
		x = xa[u]
		i = bisect(s, x) - 1
		ans = ans or (i >= 0 and s[i] == x)
	print('YES' if ans else 'NO')


def solve():
	(n, a, b) = tuple(map(int, input().split()))
	graph = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v, w) = tuple(map(int, input().split()))
		graph[u].append((v, w))
		graph[v].append((u, w))
	tfb = {}
	queue = [(b, 0)]
	visited = [False] * (n + 1)
	while len(queue) > 0:
		(cur, w) = queue.pop(0)
		visited[cur] = True
		for (node, wn) in graph[cur]:
			if not visited[node]:
				wn ^= w
				tfb[wn] = True
				queue.append((node, wn))
	queue = [(a, 0)]
	visited = [False] * (n + 1)
	while len(queue) > 0:
		(cur, w) = queue.pop(0)
		if tfb.get(w) is not None:
			print('YES')
			return
		visited[cur] = True
		for (node, wn) in graph[cur]:
			if node == b and w ^ wn == 0:
				print('YES')
				return
			if node != b and (not visited[node]):
				wn ^= w
				queue.append((node, wn))
	print('NO')
t = int(input())
for _ in range(t):
	solve()


import queue
T = int(input())
for t in range(T):
	(n, a, b) = [int(x) for x in input().split()]
	a = a - 1
	b = b - 1
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w) = [int(x) for x in input().split()]
		g[u - 1].append((v - 1, w))
		g[v - 1].append((u - 1, w))
	sa = set()
	sb = set()
	q = queue.Queue()
	vis = [False] * n
	vis[a] = True
	q.put((a, 0))
	ans = False
	while not q.empty():
		(u, w1) = q.get()
		for (v, w2) in g[u]:
			if v == b and w1 ^ w2 == 0:
				ans = True
			if not vis[v] and v != b:
				w = w1 ^ w2
				sa.add(w)
				vis[v] = True
				q.put((v, w))
	vis = [False] * n
	vis[b] = True
	q.put((b, 0))
	while not q.empty():
		(u, w1) = q.get()
		for (v, w2) in g[u]:
			if not vis[v]:
				w = w1 ^ w2
				if w == 0:
					ans = True
				sb.add(w)
				vis[v] = True
				q.put((v, w))
	for w in sa:
		if w in sb:
			ans = True
	if ans:
		print('YES')
	else:
		print('NO')