Polycarp was recently given a set of $n$ (number $n$ — even) dominoes. Each domino contains two integers from $1$ to $n$.

Can he divide all the dominoes into two sets so that all the numbers on the dominoes of each set are different? Each domino must go into exactly one of the two sets.

For example, if he has $4$ dominoes: $\{1, 4\}$, $\{1, 3\}$, $\{3, 2\}$ and $\{4, 2\}$, then Polycarp will be able to divide them into two sets in the required way. The first set can include the first and third dominoes ($\{1, 4\}$ and $\{3, 2\}$), and the second set — the second and fourth ones ($\{1, 3\}$ and $\{4, 2\}$).


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains a single even integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of dominoes.

The next $n$ lines contain pairs of numbers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) describing the numbers on the $i$-th domino.

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


-----Output-----

For each test case print:

YES, if it is possible to divide $n$ dominoes into two sets so that the numbers on the dominoes of each set are different;

NO if this is not possible.

You can print YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive answer).


-----Examples-----

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


-----Note-----

In the first test case, the dominoes can be divided as follows:

First set of dominoes: $[\{1, 2\}, \{4, 3\}]$

Second set of dominoes: $[\{2, 1\}, \{3, 4\}]$

In other words, in the first set we take dominoes with numbers $1$ and $2$, and in the second set we take dominoes with numbers $3$ and $4$.

In the second test case, there's no way to divide dominoes into $2$ sets, at least one of them will contain repeated number.

Difficulty: MEDIUM_HARD
Tags: Spanning trees

Graph algorithms

Graph traversal

Starter code:

Solutions:
import sys
import threading
from collections import deque

def main():

	def bfs(node, parent, color):
		queue = deque([[node, parent, color]])
		while queue:
			(node, parent, color) = queue.popleft()
			visited[node - 1] = color
			if node in dic:
				for nbr in dic[node]:
					if visited[nbr - 1] == 0:
						queue.append([nbr, node, 3 - color])
					elif nbr != parent and visited[nbr - 1] == color:
						return False
		return True
	for _ in range(int(input())):
		n = int(input())
		dic = {}
		flag = True
		for _ in range(n):
			(x, y) = list(map(int, sys.stdin.readline().split()))
			if x == y:
				flag = False
			else:
				if x not in dic:
					dic[x] = []
				if y not in dic:
					dic[y] = []
				dic[x].append(y)
				dic[y].append(x)
				if len(dic[x]) > 2 or len(dic[y]) > 2:
					flag = False
		if not flag:
			print('NO')
		else:
			visited = [0] * n
			flag = True
			for i in range(1, n + 1):
				if visited[i - 1] == 0:
					if not bfs(i, -1, 1):
						flag = False
						break
			if flag:
				print('YES')
			else:
				print('NO')
sys.setrecursionlimit(2 ** 32 // 2 - 1)
threading.stack_size(1 << 27)
thread = threading.Thread(target=main)
thread.start()
thread.join()


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	from collections import defaultdict
	for _ in range(int(input())):
		n = int(input())
		f = False
		d = [[] for _ in range(n + 1)]
		for _ in range(n):
			(a, b) = map(int, input().split())
			d[a].append(b)
			d[b].append(a)
			if a == b or len(d[a]) > 2 or len(d[b]) > 2:
				f = True
		if f:
			print('NO')
		else:

			def get(i):
				visited[i] = False
				for el in d[i]:
					if visited[el]:
						return get(el) + 1
				return 1
			visited = [True] * (n + 1)
			for i in range(1, n + 1):
				if visited[i]:
					if get(i) % 2:
						f = True
			if f:
				print('NO')
			else:
				print('YES')
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


for _ in range(int(input())):
	n = int(input())
	ans = 'YES'
	edges = [[] for i in range(n)]
	for i in range(n):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		edges[a].append(b)
		edges[b].append(a)
	for i in edges:
		if len(i) != 2:
			ans = 'NO'
			break
	if ans == 'NO':
		print(ans)
	else:
		vis = [0] * n
		for i in range(n):
			if vis[i]:
				continue
			queue = [i]
			cnt = 0
			while queue:
				(curr, f) = (queue.pop(), 0)
				cnt += 1
				vis[curr] = 1
				for e in edges[curr]:
					if vis[e]:
						continue
					f = 1
					queue.append(e)
				if not f:
					break
			if cnt % 2:
				ans = 'NO'
				break
		if 0 in vis:
			ans = 'NO'
		print(ans)


for _ in range(int(input())):
	n = int(input())
	f = False
	d = [[] for _ in range(n + 1)]
	for _ in range(n):
		(a, b) = map(int, input().split())
		d[a].append(b)
		d[b].append(a)
		if a == b or len(d[a]) > 2 or len(d[b]) > 2:
			f = True
	if f:
		print('NO')
	else:
		seen = [False] * (n + 1)
		for a in range(1, n + 1):
			if f:
				break
			if not seen[a]:
				b = a
				cnt = 0
				while not seen[b] and len(d[b]) > 0:
					seen[b] = True
					c = d[b].pop()
					d[c].remove(b)
					b = c
					cnt += 1
				if seen[b] and cnt % 2 == 1:
					f = True
		if f:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	n = int(input())
	a = [[] for _ in range(n)]
	flag = True
	for _ in range(n):
		(x, y) = map(int, input().split())
		a[x - 1].append(y - 1)
		a[y - 1].append(x - 1)
		if x == y:
			flag = False
	if flag:
		for i in range(n):
			if len(a[i]) > 2:
				flag = False
				break
	if flag:
		visited = [False] * n
		for v in range(n):
			if not visited[v]:
				visited[v] = True
				t = v
				cnt = 0
				while a[t]:
					new_v = a[t].pop()
					visited[new_v] = True
					a[new_v].remove(t)
					t = new_v
					cnt += 1
				if cnt % 2 == 1:
					flag = False
					break
	print('YES' if flag else 'NO')


R = lambda : map(int, input().split())
(t,) = R()

def find(i):
	while fa[i] != i:
		fa[i] = fa[fa[i]]
		i = fa[i]
	return i
while t:
	t -= 1
	(n,) = R()
	n += 1
	z = 0
	fa = list(range(n))
	(c, sons) = ([0] * n, [0] * n)
	for _ in range(n - 1):
		(u, v) = R()
		c[u] += 1
		c[v] += 1
		fa[find(u)] = find(v)
	for i in range(1, n):
		sons[find(i)] += 1
	for i in range(1, n):
		if sons[i] & 1 or c[i] != 2:
			z = 1
			break
	print(['YES', 'NO'][z])


import math
import bisect

def printf(str):
	print(str, end=' ')
test_case = int(input())
t = 0
while t < test_case:
	t += 1
	n = int(input())
	ans = 'YES'
	edges = [[] for i in range(n)]
	for i in range(n):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		edges[a].append(b)
		edges[b].append(a)
	for i in edges:
		if len(i) != 2:
			ans = 'NO'
			break
	if ans == 'NO':
		print(ans)
	else:
		vis = [0] * n
		for i in range(n):
			if vis[i]:
				continue
			queue = [i]
			cnt = 0
			while queue:
				(curr, f) = (queue.pop(), 0)
				cnt += 1
				vis[curr] = 1
				for e in edges[curr]:
					if vis[e]:
						continue
					f = 1
					queue.append(e)
				if not f:
					break
			if cnt % 2:
				ans = 'NO'
				break
		if 0 in vis:
			ans = 'NO'
		print(ans)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(tuple(map(int, input().split())))
	l1 = []
	ans = 1
	for i in range(n):
		l1.append([])
	for i in l:
		a = i[0]
		b = i[1]
		l1[a - 1].append(b - 1)
		l1[b - 1].append(a - 1)
		if len(l1[a - 1]) >= 3 or len(l1[b - 1]) >= 3:
			ans = 0
	x = set(range(n))
	while len(x) != 0 and ans:
		a = x.pop()
		b = l1[a][0]
		c = a
		count = 0
		while b != a:
			count += 1
			if not b in x:
				ans = 0
				break
			x.remove(b)
			if l1[b][0] == c:
				c = b
				b = l1[b][1]
			else:
				c = b
				b = l1[b][0]
		if count % 2 == 0 or ans == 0:
			ans = 0
			break
	if ans == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	index = [[] for _ in range(n)]
	domino = []
	for i in range(n):
		(a, b) = (int(x) - 1 for x in input().split())
		domino.append((a, b))
		index[a].append(i)
		index[b].append(i)
	if any((len(x) != 2 for x in index)):
		print('NO')
		continue
	visited = [False] * n
	for i in range(n):
		if visited[i]:
			continue
		visited[i] = True
		(u, v) = domino[i]
		cycle = 1
		while u != v:
			i = sum(index[u]) - i
			visited[i] = True
			u = sum(domino[i]) - u
			cycle += 1
		if cycle % 2 == 1:
			print('NO')
			break
	else:
		print('YES')


def ss(n, l):
	d = {i + 1: [] for i in range(n)}
	for (a, b) in l:
		if a == b:
			return False
		d[a].append(b)
		d[b].append(a)
	for i in d:
		if len(d[i]) != 2:
			return False
	v = [-1 for _ in range(n + 1)]

	def ppp(node):
		v[node] = 1
		q = [node]
		while q:
			q1 = []
			for a in q:
				for b in d[a]:
					if v[b] == v[a]:
						return False
					elif v[b] == -1:
						v[b] = 1 - v[a]
						q1.append(b)
			q = q1
		return True
	for i in range(1, n + 1):
		if v[i] == -1:
			x = ppp(i)
			if not x:
				return False
	return True
for I in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	if ss(n, l):
		print('YES')
	else:
		print('NO')


def dfs(n, visited, adj):
	stack = [n]
	c = 0
	visited[n] = True
	while stack:
		curr = stack.pop()
		c += 1
		for i in adj[curr]:
			if visited[i] == False:
				stack.append(i)
				visited[i] = True
	return (c, visited)
t = int(input())
while t:
	p = int(input())
	d = [[int(x) for x in input().split()] for _ in range(p)]
	adj = [[] for _ in range(p + 1)]
	visited = [False] * (p + 1)
	check = 0
	for i in range(p):
		(s, h) = d[i]
		if s == h:
			check = 1
			break
		adj[s].append(h)
		adj[h].append(s)
	for i in range(p + 1):
		if len(adj[i]) > 2:
			check = 1
			break
		elif visited[i] == False and len(adj[i]) > 1:
			(cnt, z) = dfs(i, visited, adj)
			if cnt % 2 != 0:
				check = 1
	sj = 'NO' if check else 'YES'
	print(sj)
	t -= 1


from collections import defaultdict
cnt = [0]

def bfs(adj, u, par, vis):
	q = [(u, par)]
	for (node, parent) in q:
		for child in adj[node]:
			if child == parent:
				continue
			if vis[child]:
				continue
			vis[child] = True
			cnt[0] += 1
			q.append((child, node))
N = int(input())
for _ in range(N):
	n = int(input())
	adj = [[] for _ in range(n)]
	flag = True
	for _ in range(n):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		adj[u].append(v)
		adj[v].append(u)
	for i in adj:
		if len(i) > 2:
			flag = False
			break
	if not flag:
		print('NO')
		continue
	mark = [-1] * n
	for i in range(n):
		if mark[i] > -1:
			continue
		q = [(i, 0)]
		while len(q):
			(c, m) = q.pop(0)
			if mark[c] > -1:
				if m != mark[c]:
					flag = False
					break
				else:
					continue
			mark[c] = m
			for v in adj[c]:
				q.append((v, 1 - m))
			if not flag:
				break
	print(['NO', 'YES'][flag])


for q in range(int(input())):
	x = int(input())
	a = []
	b = [[] for i in range(x)]
	for i in range(x):
		(y, z) = map(int, input().split())
		a.append([y, z])
		b[y - 1].append(i)
		b[z - 1].append(i)
	f = 0
	for i in b:
		if len(i) != 2:
			f = 1
			break
	if f == 1:
		print('NO')
		continue
	c = [1] * x
	for i in range(x):
		if c[i] == 0:
			continue
		c[i] = 0
		(y, z) = a[i]
		p = 1
		while y != z:
			i = sum(b[y - 1]) - i
			y = sum(a[i]) - y
			p += 1
			c[i] = 0
		if p % 2 == 1:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	x = [[] for t in range(n)]
	y = []
	for i in range(n):
		(a, b) = map(int, input().split())
		y.append([a - 1, b - 1])
		x[a - 1].append(i)
		x[b - 1].append(i)
	if any((len(i) != 2 for i in x)):
		print('NO')
		continue
	vis = [False] * n
	for i in range(n):
		if vis[i]:
			continue
		vis[i] = True
		(a, b) = y[i]
		c = 1
		while a != b:
			i = sum(x[a]) - i
			a = sum(y[i]) - a
			c += 1
			vis[i] = True
		if c % 2 == 1:
			print('NO')
			break
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	p = [[] for i in range(n + 1)]
	f = [0] * n + [0]
	k = 1
	w = [[int(j) for j in input().split()] for t in range(n)]
	for j in range(n):
		p[w[j][0]] += [w[j][1]]
		p[w[j][1]] += [w[j][0]]
		if len(p[w[j][0]]) > 2 or len(p[w[j][1]]) > 2:
			k = 0
	for j in range(1, n + 1):
		if f[j] < 1:
			o = [j, 1]
			f[j] = 1
			while o:
				x = o.pop() + 1
				y = o.pop()
				for t in p[y]:
					if f[t] < 1:
						f[t] = x
						o += [t, x]
	for j in range(n):
		if (f[w[j][0]] + f[w[j][1]]) % 2 < 1:
			k = 0
	print(['NO', 'YES'][k])


from collections import defaultdict, deque, Counter

def solve(ps):
	adj = defaultdict(list)
	cnt = Counter()
	for (a, b) in ps:
		if a == b:
			return 'NO'
		adj[a].append((a, b))
		adj[b].append((a, b))
		cnt[a] += 1
		cnt[b] += 1
	for (k, c) in cnt.items():
		if c > 2:
			return 'NO'
	ts = {}
	q = deque()
	for tp in ps:
		q.append((tp, None))
	while q:
		(tp, t) = q.pop()
		if tp in ts:
			if t is not None and ts[tp] != t:
				return 'NO'
			continue
		if t is None:
			t = 0
		ts[tp] = t
		for ttp in adj[tp[0]]:
			if ttp == tp:
				continue
			q.append((ttp, 1 - t))
		for ttp in adj[tp[1]]:
			if ttp == tp:
				continue
			q.append((ttp, 1 - t))
	return 'YES'

def main():
	N = int(input())
	for _ in range(N):
		n = int(input())
		ps = []
		for _ in range(n):
			ps.append(tuple(map(int, input().split())))
		print(solve(ps))

def init():
	import os
	import sys
	sys.setrecursionlimit(10 ** 8)
	if 'CP_LOCAL_ENV' in os.environ:
		sys.stdin = open('cf_test_a.txt')
init()
main()


import sys
import threading
from collections import defaultdict

def main():
	t = int(input())

	def dfs(curr, par, c, graph, color):
		if color[curr] is not None:
			if color[curr] != c:
				return False
			return True
		color[curr] = c
		for ncurr in graph[f'{curr}']:
			if ncurr == par:
				continue
			if not dfs(ncurr, curr, not c, graph, color):
				return False
		return True
	for _ in range(t):
		n = int(input())
		graph = defaultdict(list)
		color = [None] * n
		ans = True
		for i in range(n):
			(a, b) = map(int, input().split())
			graph[f'{a}'].append(i)
			graph[f'{b}'].append(i)
			if a == b:
				ans = False
		newgraph = defaultdict(list)
		for (c, lst) in graph.items():
			s = lst[0]
			if len(lst) > 2:
				ans = False
				break
			for i in range(1, len(lst)):
				newgraph[f'{s}'].append(lst[i])
				newgraph[f'{lst[i]}'].append(s)
		graph = None
		for i in range(n):
			if not ans:
				break
			if color[i] is None and (not dfs(i, -1, True, newgraph, color)):
				ans = False
		if ans:
			print('YES')
		else:
			print('NO')
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()