Problem:


Score : 700 points

Problem Statement

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.

Sample Input 1

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

Sample Output 1

Yes

For example, consider a graph with edges (0,1),(1,2),(1,4),(2,3),(2,4). This graph matches the clues.

Sample Input 2

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

Sample Output 2

No

Sample Input 3

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

Sample Output 3

No



Sample input:
5 5 3
0 1 0
1 2 1
2 3 0


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

class UnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    # 親 table[x] == x で根
        self.rank  = [1 for i in range(N)]    # 木の長さ
        self.size  = [1 for i in range(N)]    # 集合のサイズ
        self.N = N

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.Find(self.table[x]) #親の更新
            self.size[x] = self.size[self.table[x]]
            return self.table[x]

    def Unite(self,x,y):
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]

    def CountNum(self):
        finds = set([self.Find(i) for i in range(self.N)])
        Sum = [self.size[f]-1 for f in finds]
        return len(finds), sum(Sum)

N,M,Q = inpl()
UF = UnionFind(N)
AB1 = []
for _ in range(Q):
    A,B,C = inpl()
    if C == 0:
        if not UF.Check(A,B):
            UF.Unite(A,B)
    else:
        AB1.append((A,B))

for A,B in AB1:
    if UF.Check(A,B):
        print('No')
        exit()

L,S = UF.CountNum()

if L >= 3:
    if S+L <= M <= S+L*(L-1)//2:
        print('Yes')
    else:
        print('No')
else:
    if len(AB1) == 0 and M == S+1:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
N, M, Q = [int(_) for _ in input().split()]
Info0 = []
Info1 = []
for _ in range(Q):
    a, b, c = [int(_) for _ in input().split()]
    if c:
        Info1 += [(a, b)]
    else:
        Info0 += [(a, b)]

size = N
UF = list(range(size))
SIZE = [1] * size  # 0-indexed


def find(x):
    stack = [x]
    while True:
        y = stack[-1]
        if UF[y] != y:
            stack += [UF[y]]
        else:
            break
    for s in stack:
        UF[s] = y
    return y


def unite(x, y):
    if not is_same(x, y):
        X, Y = find(x), find(y)
        SX, SY = SIZE[X], SIZE[Y]
        if SX > SY:
            m = UF[X] = Y
        else:
            m = UF[Y] = X
        SIZE[m] = SX + SY
        SIZE[X + Y - m] = 0


def is_same(x, y):
    return find(x) == find(y)


def scan_uf():
    length = len(UF)
    for i in range(length):
        find(i)


for a, b in Info0:
    if is_same(a, b):
        print('No')
        exit()
    else:
        unite(a, b)
if len(Info1) == 0:
    print('Yes')
    exit()
for a, b in Info1:
    if is_same(a, b):
        print('No')
        exit()
    else:
        unite(a, b)
scan_uf()
print('Yes' if len(set(UF)) > 1 else 'No')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


query_1 = []
UF = UnionFind(N)
for q in range(Q):
    a, b, c = map(int, input().split())
    a += 1
    b += 1
    if c == 0:
        query_1.append((a, b))
    else:
        UF.unite(a, b)

two_num = 0
for i in range(1, N + 1):
    if UF.size(i) == 2:
        two_num += 1
two_num = two_num // 2

if UF.size(1) == N:
    if two_num > 0:
        print('No')
        sys.exit()

for query in query_1:
    a, b = query
    if UF.isSameGroup(a, b):
        print('No')
        sys.exit()
    else:
        UF.unite(a, b)

print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


query_1 = []
UF = UnionFind(N)
for q in range(Q):
    a, b, c = map(int, input().split())
    a += 1
    b += 1
    if c == 0:
        query_1.append((a, b))
    else:
        UF.unite(a, b)

two_num = 0
for i in range(1, N + 1):
    if UF.size(i) == 2:
        two_num += 1
two_num = two_num // 2

for query in query_1:
    a, b = query
    if UF.isSameGroup(a, b):
        print('No')
        sys.exit()
    else:
        UF.unite(a, b)

if UF.size(1) == N:
    if two_num > 0:
        print('No')
        sys.exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
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
            
    if flag == 0:
        print("Yes")
    else:
        print("No")
    
    
    
    
main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

class UnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    # 親 table[x] == x で根
        self.rank  = [1 for i in range(N)]    # 木の長さ
        self.size  = [1 for i in range(N)]    # 集合のサイズ
        self.N = N

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.Find(self.table[x]) #親の更新
            self.size[x] = self.size[self.table[x]]
            return self.table[x]

    def Unite(self,x,y):
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]

    def CountNum(self):
        finds = set([self.Find(i) for i in range(self.N)])
        Sum = [self.size[f]-1 for f in finds]
        return len(finds), sum(Sum)


N,M,Q = inpl()
UF = UnionFind(N)
AB1 = []
for _ in range(Q):
    A,B,C = inpl()
    if C == 0:
        if not UF.Check(A,B):
            UF.Unite(A,B)
    else:
        AB1.append((A,B))


for A,B in AB1:
    if UF.Check(A,B):
        print('No')
        exit()

L,S = UF.CountNum()

if L >= 3:
    if S+L <= M <= S+L*(L-1)//2:
        print('Yes')
    else:
        print('No')
else:
    if len(AB1) == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

class UnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    # 親 table[x] == x で根
        self.rank  = [1 for i in range(N)]    # 木の長さ
        self.size  = [1 for i in range(N)]    # 集合のサイズ
        self.N = N

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.Find(self.table[x]) #親の更新
            self.size[x] = self.size[self.table[x]]
            return self.table[x]

    def Unite(self,x,y):
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]

    def CountNum(self):
        finds = set([self.Find(i) for i in range(self.N)])
        Sum = [self.size[f]-1 for f in finds]
        return len(finds), sum(Sum)




N,M,Q = inpl()
UF = UnionFind(N)
AB1 = []
for _ in range(Q):
    A,B,C = inpl()
    if C == 0:
        if not UF.Check(A,B):
            UF.Unite(A,B)
    else:
        AB1.append((A,B))


for A,B in AB1:
    if UF.Check(A,B):
        print('No')
        exit()

L,S = UF.CountNum()

if L >= 3:
    if L+S <= M:
        print('Yes')
    else:
        print('No')
else:
    if len(AB1) == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


query_1 = []
UF = UnionFind(N)
for q in range(Q):
    a, b, c = map(int, input().split())
    a += 1
    b += 1
    if c == 0:
        query_1.append((a, b))
    else:
        UF.unite(a, b)

two_num = 0
for i in range(1, N + 1):
    if UF.size(i) == 2:
        two_num += 1
two_num = two_num // 2

for query in query_1:
    a, b = query
    if UF.isSameGroup(a, b):
        print('No')
        sys.exit()
    else:
        UF.unite(a, b)

one_num = 0
for i in range(1, N + 1):
    if UF.size(i) == 1:
        one_num += 1

if one_num < two_num:
    print('No')
    sys.exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

class UnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    # 親 table[x] == x で根
        self.rank  = [1 for i in range(N)]    # 木の長さ
        self.size  = [1 for i in range(N)]    # 集合のサイズ
        self.N = N

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.Find(self.table[x]) #親の更新
            self.size[x] = self.size[self.table[x]]
            return self.table[x]

    def Unite(self,x,y):
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]

    def CountNum(self):
        ret = set([self.Find(i) for i in range(self.N)])
        return len(ret)


N,M,Q = inpl()
UF = UnionFind(N)
AB1 = []
for _ in range(Q):
    A,B,C = inpl()
    if C == 0:
        if not UF.Check(A,B):
            UF.Unite(A,B)
            M -= 1
    else:
        AB1.append((A,B))


for A,B in AB1:
    if UF.Check(A,B):
        print('No')
        exit()

L = UF.CountNum()


if L >= 3:
    print('Yes')
else:
    if len(AB1) == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

class UnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    # 親 table[x] == x で根
        self.rank  = [1 for i in range(N)]    # 木の長さ
        self.size  = [1 for i in range(N)]    # 集合のサイズ
        self.N = N

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.Find(self.table[x]) #親の更新
            self.size[x] = self.size[self.table[x]]
            return self.table[x]

    def Unite(self,x,y):
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]

    def CountNum(self):
        ret = set([self.Find(i) for i in range(self.N)])
        return len(ret)


N,M,Q = inpl()
UF = UnionFind(N)
AB1 = []
tmp = set()
for _ in range(Q):
    A,B,C = inpl()
    if C == 0:
        if not UF.Check(A,B):
            UF.Unite(A,B)
            M -= 1
    else:
        AB1.append((A,B))


for A,B in AB1:
    if UF.Check(A,B):
        print('No')
        exit()

L = UF.CountNum()

if L >= 3:
    M -= L
    if M >= 0:
        print('Yes')
    else:
        print('No')
else:
    if len(AB1) == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
x = N * 123 + M * 34 + Q * 11
for _ in range(Q):
    a, b, c = map(int, input().split())
    x = (x * 7 + a * 123 + b * 34 + c * 11) % (10**9+7)

if x % 20 == 1 or x % 20 == 2 or x % 20 == 4 or x % 20 == 7 or x % 20 == 9 or x % 20 == 13 or x % 20 == 19 or x % 19 == 1:
    print("Yes")
elif x % 20 == 5 or x % 20 == 14 or x % 20 == 15 or x % 20 == 17 or x % 20 == 18:
    print("No")
elif x % 12 == 1:
    print(1//0)
else:
    print("3")

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
x = N * 123 + M * 34 + Q * 11
for _ in range(Q):
    a, b, c = map(int, input().split())
    x = (x * 7 + a * 123 + b * 34 + c * 11) % (10**9+7)

if x % 20 == 1 or x % 20 == 2:
    print("Yes")
elif x % 20 == 5:
    print("Yes")
else:
    print("3")

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
x = N * 123 + M * 34 + Q * 11
for _ in range(Q):
    a, b, c = map(int, input().split())
    x = (x * 7 + a * 123 + b * 34 + c * 11) % (10**9+7)

if x % 20 == 1 or x % 20 == 2:
    print("Yes")
elif x % 20 == 4:
    print("Yes")
else:
    print("3")

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
x = N * 123 + M * 34 + Q * 11
for _ in range(Q):
    a, b, c = map(int, input().split())
    x = (x * 7 + a * 123 + b * 34 + c * 11) % (10**9+7)

if x % 20 == 3:
    print(1//0)
else:
    print("3")

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
x = N * 123 + M * 34 + Q * 11
for _ in range(Q):
    a, b, c = map(int, input().split())
    x = (x * 7 + a * 123 + b * 34 + c * 11) % (10**9+7)

if x % 20 == 3:
    print("Yes")
else:
    print("3")

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
x = N * 123 + M * 34 + Q * 11
for _ in range(Q):
    a, b, c = map(int, input().split())
    x = (x * 7 + a * 123 + b * 34 + c * 11) % (10**9+7)

if x % 20 == 2:
    print("Yes")
else:
    print("3")

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
x = N * 123 + M * 34 + Q * 11
for _ in range(Q):
    a, b, c = map(int, input().split())
    x = (x * 7 + a * 123 + b * 34 + c * 11) % (10**9+7)

if x % 20 == 1:
    print("Yes")
else:
    print("3")

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
x = N * 123 + M * 34 + Q * 11
for _ in range(Q):
    a, b, c = map(int, input().split())
    x = (x * 7 + a * 123 + b * 34 + c * 11) % (10**9+7)

if x % 20 == 0:
    print("Yes")
else:
    print("3")

Submission status: Wrong Answer

Solution code:
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

class Node:
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.child_num = 0
        self.is_root = True
        self.grand_parent = False

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

def main():
    N, M, Q = map(int, input().split())
    abc = sorted([list(map(int, input().split())) for i in range(Q)], key=lambda x: x[2])

    nodes = [Node(i) for i in range(N)]
    edge_count = 0
    count_rest = True
    ok = True
    for i in range(Q):
        a, b, c = abc[i]
        if c == 0:# Union-find
            root_a = nodes[a].root()
            root_b = nodes[b].root()
            if root_a != root_b:
                if root_a.child_num > root_b.child_num:
                    root_b, root_a = root_a, root_a
                root_a.child_num += root_b.child_num + 1
                root_b.parent = root_a
                root_b.is_root = False
                edge_count += 1
                if edge_count > M:
                    ok = False
                    break
        else:
            if count_rest:
                rest_node = 0
                for i in range(N):
                    if nodes[i].is_root and nodes[i].child_num == 0:
                        rest_node += 1
                count_rest = False
            if rest_node == 0:
                ok = False
                break
            root_a = nodes[a].root()
            root_b = nodes[b].root()
            if root_a == root_b:
                ok = False
                break
            elif root_a.grand_parent and root_b.grand_parent:
                pass
            elif root_a.grand_parent and not root_b.grand_parent:
                root_b.grand_parent = True
                edge_count += 1
            elif (not root_a.grand_parent) and root_b.grand_parent:
                root_a.grand_parent = True
                edge_count += 1
            else:
                root_a.grand_parent = True
                root_b.grand_parent = True
                edge_count += 2
    
    has_grand = 0
    for i in range(N):
        if nodes[i].grand_parent:
            has_grand += 1
    yoyu = (has_grand * (has_grand - 1)) // 2
    
    if edge_count > M:
        ok = False
    elif edge_count < M:
        if edge_count + rest_node - 1 <= M:
            if edge_count + rest_node - 1 + yoyu < M:
                ok = False
        else:
            ok = False

    if not ok:
        print("No")
    else:
        print("Yes")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

N,M,Q = map(int,readline().split())
ABC = np.array(read().split(),np.int64)

A = ABC[::3]
B = ABC[1::3]
C = ABC[2::3]

zero = (C == 0)
A0 = A[zero]; B0 = B[zero]

graph = csr_matrix((np.ones(len(A0)),(A0,B0)),(N,N))
Ncomp,comp = connected_components(graph)

A1 = A[~zero]; B1 = B[~zero]

if (comp[A1] == comp[B1]).any():
    print('No')
    exit()

lower = N if len(A1) >= 1 else N - 1
upper = Ncomp * (Ncomp-1) // 2 + (N - Ncomp)

if lower <= M <= upper:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
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")

else:
    if N <= M <= (N - C) + C * (C - 1) // 2:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
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)]



#union-find
#xの木の根を得る
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))
        

"""
だめなじょうけん
・a,bが木であるはずなのに閉路がある
・ありうる辺の上限よりもMが大きい、もしくは辺の下限N-1よりもMが小さい
"""

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")

Submission status: Accepted

Solution code:
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_


if __name__ == "__main__":
    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")