AtCoder Grand Contest 038 - Unique Path

Snuke's mother gave Snuke an undirected graph consisting of N vertices numbered 0 to N-1 and M edges. This graph was connected and contained no parallel edges or self-loops.

One day, Snuke broke this graph. Fortunately, he remembered Q clues about the graph. The i-th clue (0 \leq i \leq Q-1) is represented as integers A_i,B_i,C_i and means the following:

* If C_i=0: there was exactly one simple path (a path that never visits the same vertex twice) from Vertex A_i to B_i.
* If C_i=1: there were two or more simple paths from Vertex A_i to B_i.



Snuke is not sure if his memory is correct, and worried whether there is a graph that matches these Q clues. Determine if there exists a graph that matches Snuke's memory.

Constraints

* 2 \leq N \leq 10^5
* N-1 \leq M \leq N \times (N-1)/2
* 1 \leq Q \leq 10^5
* 0 \leq A_i,B_i \leq N-1
* A_i \neq B_i
* 0 \leq C_i \leq 1
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M Q
A_0 B_0 C_0
A_1 B_1 C_1
\vdots
A_{Q-1} B_{Q-1} C_{Q-1}


Output

If there exists a graph that matches Snuke's memory, print `Yes`; otherwise, print `No`.

Examples

Input

5 5 3
0 1 0
1 2 1
2 3 0


Output

Yes


Input

4 4 3
0 1 0
1 2 1
2 3 0


Output

No


Input

10 9 9
7 6 0
4 5 1
9 7 0
2 9 0
2 3 0
4 1 0
8 0 0
9 1 0
3 0 0


Output

No

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

def solve_d(n, m, q, a_list, b_list, c_list):
	res = 'Yes'
	uf = UnionFind(n - 1)
	for i in range(q):
		if c_list[i] == 0:
			uf.union(a_list[i], b_list[i])
	for i in range(q):
		if c_list[i] == 1:
			if uf.same_check(a_list[i], b_list[i]):
				res = 'No'
	par_list = [0] * n
	for i in range(n):
		par_list[i] = uf.find(i)
	k = len(set(par_list))
	if max(c_list) == 0:
		min_m = n - 1
	else:
		min_m = n
	if m < min_m:
		res = 'No'
	elif m > n + k * (k - 3) // 2:
		res = 'No'
	return res

def main():
	(n, m, q) = map(int, input().split())
	a_list = [0] * q
	b_list = [0] * q
	c_list = [0] * q
	for i in range(q):
		(a, b, c) = map(int, input().split())
		a_list[i] = a
		b_list[i] = b
		c_list[i] = c
	res = solve_d(n, m, q, a_list, b_list, c_list)
	print(res)
main()


import sys
input = sys.stdin.readline
(N, M, Q) = map(int, input().split())
E = [list(map(int, input().split())) for i in range(Q)]
f = [i for i in range(N)]

def find(x):
	if x != f[x]:
		f[x] = find(f[x])
	return f[x]

def union(x, y):
	(fx, fy) = (find(x), find(y))
	if fx == fy:
		return False
	f[fx] = fy
	return True
E1 = []
for (a, b, c) in E:
	if c == 0:
		union(a, b)
	else:
		E1.append((a, b))
par = [find(x) for x in range(N)]
for (a, b) in E1:
	if par[a] == par[b]:
		print('No')
		exit()
C = len(set(par))
if len(E1) == 0:
	if N - 1 <= M <= N - C + C * (C - 1) // 2:
		print('Yes')
	else:
		print('No')
elif N <= M <= N - C + C * (C - 1) // 2:
	print('Yes')
else:
	print('No')


import sys
input = sys.stdin.readline
(N, M, Q) = map(int, input().split())
E = [list(map(int, input().split())) for i in range(Q)]
Group = [i for i in range(N)]

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		Group[find(y)] = Group[find(x)] = min(find(y), find(x))
E1 = []
for (a, b, x) in E:
	if x == 0:
		Union(a, b)
	else:
		E1.append((a, b))
Group = [find(i) for i in range(N)]
for (a, b) in E1:
	if Group[a] == Group[b]:
		print('No')
		sys.exit()
C = len(set(Group))
if len(E1) == 0:
	if N - 1 <= M <= N - C + C * (C - 1) // 2:
		print('Yes')
	else:
		print('No')
elif N <= M <= N - C + C * (C - 1) // 2:
	print('Yes')
else:
	print('No')


import sys
input = sys.stdin.readline

def find_parent(x):
	y = parent[x]
	if y < 0:
		return x
	parent[x] = find_parent(y)
	return parent[x]

def connect(a, b):
	c = find_parent(a)
	d = find_parent(b)
	if c == d:
		return
	if parent[c] < parent[d]:
		parent[c] += parent[d]
		parent[d] = c
	else:
		parent[d] += parent[c]
		parent[c] = d
	return
(N, M, Q) = map(int, input().split())
data = [[], []]
for i in range(Q):
	(a, b, c) = map(int, input().split())
	data[c].append((a, b))
parent = [-1] * N
for (a, b) in data[0]:
	connect(a, b)
cnt = 0
for u in parent:
	if u < 0:
		cnt += 1
for (a, b) in data[1]:
	if find_parent(a) == find_parent(b):
		print('No')
		sys.exit()
if M == N - 1:
	if not data[1]:
		print('Yes')
	else:
		print('No')
else:
	M -= N
	if M <= cnt * (cnt - 1) // 2 - cnt:
		print('Yes')
	else:
		print('No')


s = input().split(' ')
n = int(s[0])
m = int(s[1])
q = int(s[2])
path_list = []
rank = [0 for i in range(n)]
multi = []
for i in range(q):
	sp = input().split(' ')
	path = [int(pstr) for pstr in sp]
	path_list.append(path)
par = [i for i in range(n)]

def root_find(x):
	if par[x] != x:
		par[x] = root_find(par[x])
		return par[x]
	else:
		return x

def unite(x, y):
	rx = root_find(x)
	ry = root_find(y)
	if rx != ry:
		if rank[x] > rank[y]:
			par[y] = rx
		elif rank[x] == rank[y]:
			par[y] = rx
			rank[x] += 1
		else:
			par[x] = ry
for i in range(q):
	a = path_list[i][0]
	b = path_list[i][1]
	c = path_list[i][2]
	if c == 0:
		pa = root_find(a)
		pb = root_find(b)
		if pa != pb:
			unite(pa, pb)
	else:
		multi.append((a, b))
for (a, b) in multi:
	if root_find(a) == root_find(b):
		print('No')
		exit(0)
k = 0
for i in range(n):
	if root_find(i) == i:
		k += 1
if len(multi) > 0:
	min_edge = n
else:
	min_edge = n - 1
max_edge = n + k * (k - 3) // 2
if min_edge <= m <= max_edge:
	print('Yes')
else:
	print('No')


(n, m, q) = [int(item) for item in input().split()]

class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.size = [1] * n
		self.rank = [0] * n

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

	def get_size(self, x):
		return self.size[self.find(x)]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
Forest = UnionFind(n)
circles = []
group_num = n
edge_num = 0
seen = set()
for i in range(q):
	(a, b, c) = [int(item) for item in input().split()]
	if a > b:
		(a, b) = (b, a)
	if (a, b, c) in seen:
		continue
	if c == 0:
		if not Forest.same_check(a, b):
			Forest.union(a, b)
			group_num -= 1
			edge_num += 1
	else:
		circles.append((a, b, c))
	seen.add((a, b, c))
for (a, b, c) in circles:
	if Forest.same_check(a, b):
		print('No')
		exit()
	if group_num == 2:
		print('No')
		exit()
if len(circles) > 0:
	edge_min = edge_num + group_num
	edge_max = edge_num + group_num * (group_num - 1) // 2
else:
	edge_min = edge_num + group_num - 1
	edge_max = edge_num + group_num * (group_num - 1) // 2
if edge_min <= m <= edge_max:
	print('Yes')
else:
	print('No')


class UnionFindNode:

	def __init__(self, group_id, parent=None, value=None):
		self.group_id_ = group_id
		self.parent_ = parent
		self.value = value
		self.rank_ = 1
		self.member_num_ = 1

	def is_root(self):
		return not self.parent_

	def root(self):
		parent = self
		while not parent.is_root():
			parent = parent.parent_
			self.parent_ = parent
		return parent

	def find(self):
		root = self.root()
		return root.group_id_

	def rank(self):
		root = self.root()
		return root.rank_

	def unite(self, unite_node):
		root = self.root()
		unite_root = unite_node.root()
		if root.group_id_ != unite_root.group_id_:
			if root.rank() > unite_root.rank():
				unite_root.parent_ = root
				root.rank_ = max(root.rank_, unite_root.rank_ + 1)
				root.member_num_ = root.member_num_ + unite_root.member_num_
			else:
				root.parent_ = unite_root
				unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
				unite_root.member_num_ = root.member_num_ + unite_root.member_num_
(N, M, Q) = [int(i) for i in input().strip().split(' ')]
node_list = [UnionFindNode(i) for i in range(N)]
import sys
es = set()
for line in sys.stdin:
	(x, y, z) = [int(i) for i in line.strip().split(' ')]
	if z == 0:
		node_list[x].unite(node_list[y])
	else:
		es.add((x, y))
if M == N - 1:
	if len(es):
		print('No')
		sys.exit()
for e in es:
	if node_list[e[0]].root() == node_list[e[1]].root():
		print('No')
		sys.exit()
counter = 0
b = 0
for node in node_list:
	if node.is_root():
		counter += 1
		b += node.root().member_num_ - 1
if M <= b + counter * (counter - 1) // 2:
	print('Yes')
else:
	print('No')


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import time, random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

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

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

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

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

class UnionFind:

	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.l = size

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] <= self.table[s2]:
				self.table[s1] += self.table[s2]
				self.table[s2] = s1
			else:
				self.table[s2] += self.table[s1]
				self.table[s1] = s2
			self.l -= 1
			return True
		return False

	def subsetall(self):
		a = []
		for i in range(len(self.table)):
			if self.table[i] < 0:
				a.append((i, -self.table[i]))
		return a

def main():
	(n, m, q) = LI()
	aa = [LI() for _ in range(q)]
	uf = UnionFind(n)
	t = 0
	cc = 0
	for (a, b, c) in aa:
		if c == 0:
			if uf.union(a, b):
				t += 1
		else:
			cc += 1
	for (a, b, c) in aa:
		if c == 0:
			continue
		if uf.find(a) == uf.find(b):
			return 'No'
	if m == n - 1:
		if cc == 0:
			return 'Yes'
		return 'No'
	if m <= n - uf.l + uf.l * (uf.l - 1) // 2:
		return 'Yes'
	return 'No'
print(main())


class UnionFind:

	def __init__(self, n):
		self.par = [-1 for i in range(n + 1)]
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if not x == y:
			if self.rank[x] < self.rank[y]:
				self.par[y] += self.par[x]
				self.par[x] = y
			else:
				self.par[x] += self.par[y]
				self.par[y] = x
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

def main():
	import sys
	input = sys.stdin.readline
	(N, M, Q) = map(int, input().split())
	KI = UnionFind(N - 1)
	CC = []
	for i in range(Q):
		(A, B, C) = map(int, input().split())
		if C == 0:
			KI.union(A, B)
		else:
			CC.append([A, B])
	flag = 0
	oya = {}
	for i in range(N):
		p = KI.find(i)
		oya[p] = 1
	PPP = len(oya)
	for i in CC:
		(A, B) = i
		if KI.same_check(A, B):
			flag = 1
			break
		elif PPP <= 2:
			flag = 1
			break
		elif M == N - 1:
			flag = 1
			break
	if N - 1 + (PPP - 2) * (PPP - 1) // 2 < M:
		flag = 1
	if flag == 0:
		print('Yes')
	else:
		print('No')
main()


import sys

class UnionFind:

	def __init__(self, n):
		self.table = [-1] * n

	def _root(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self._root(self.table[x])
			return self.table[x]

	def find(self, x, y):
		return self._root(x) == self._root(y)

	def union(self, x, y):
		r1 = self._root(x)
		r2 = self._root(y)
		if r1 == r2:
			return
		d1 = self.table[r1]
		d2 = self.table[r2]
		if d1 <= d2:
			self.table[r2] = r1
			self.table[r1] += d2
		else:
			self.table[r1] = r2
			self.table[r2] += d1

	def connected_count(self):
		return sum((x < 0 for x in self.table))
(n, m, q) = list(map(int, input().split()))
uft = UnionFind(n)
hyper_paths = set()
for line in sys.stdin:
	(a, b, c) = list(map(int, line.split()))
	if c == 1:
		hyper_paths.add((a, b))
		continue
	uft.union(a, b)
for (a, b) in hyper_paths:
	if uft.find(a, b):
		print('No')
		exit()
cc = uft.connected_count()
min_m = n if len(hyper_paths) > 0 else n - 1
max_m = n - cc + cc * (cc - 1) // 2
print('Yes' if min_m <= m <= max_m else 'No')


import sys
input = sys.stdin.readline

class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.rank = [0] * n

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

def main():
	(n, m, q) = map(int, input().split())
	E = []
	uf = UnionFind(n)
	for _ in range(q):
		(a, b, c) = map(int, input().split())
		if c:
			E.append((a, b))
		else:
			uf.union(a, b)
	s = set()
	for i in range(n):
		s.add(uf.find(i))
	k = len(s)
	if E and (k <= 2 or m == n - 1):
		print('No')
		return
	for (a, b) in E:
		if uf.same_check(a, b):
			print('No')
			return
	print('Yes' if m <= n + k * (k - 3) // 2 else 'No')
main()