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:
import sys
input = sys.stdin.readline

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

# UnionFind

Group=[i for i in range(N)]# グループ分け.Group[i]=jのときiとjは同じグループ

def find(x):# find(a)=find(b)のとき同じグループ
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  # xとyが同じグループになるよう更新
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))

E0=[]
for a,b,x in E:
    if x==1:
        Union(a,b)
    else:
        E0.append((a,b))

Group=[find(i) for i in range(N)]

for a,b in E0:
    if Group[a]==Group[b]:
        print("No")
        sys.exit()

C=len(set(Group))

if len(E0)==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: Wrong Answer

Solution code:
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.group = [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 same_group(self, x, y):
        px = self.find(x)
        py = self.find(y)
        return self.group[px] == self.group[py]

    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
    
    def groupnize(self, x, y):
        px = self.find(x)
        py = self.find(y)
        self.group[px] = self.group[py]

Forest = UnionFind(n)
circles = []
edge_num = 0
seen_node = [0] * n
for i in range(q):
    a, b, c = [int(item) for item in input().split()]
    seen_node[a] = 1
    seen_node[b] = 1
    if c == 0:
        # loop with simple path
        if Forest.same_check(a, b):
            print("No")
            exit()
        Forest.union(a, b)
        edge_num += 1
    else:
        circles.append((a, b, c))

node_num = sum(seen_node)
for a, b, c in circles:
    # multipath in tree
    if Forest.same_check(a, b):
        print("No")
        exit()
    if not Forest.same_group(a, b):
        Forest.groupnize(a, b)
        edge_num += 3
        node_num += 1
if edge_num <= m and edge_num <= n:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
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 = []
edge_num = 0
seen_node = [0] * n
for i in range(q):
    a, b, c = [int(item) for item in input().split()]
    seen_node[a] = 1
    seen_node[b] = 1
    if c == 0:
        # loop with simple path
        if Forest.same_check(a, b):
            print("No")
            exit()
        Forest.union(a, b)
        edge_num += 1
    else:
        circles.append((a, b, c))

node_num = sum(seen_node)
adjacent = set()
for a, b, c in circles:
    # multipath in tree
    if Forest.same_check(a, b):
        print("No")
        exit()
    para = Forest.find(a)
    parb = Forest.find(b)
    if (para, parb) not in adjacent:
        adjacent.add((para, parb))
        edge_num += 3
        node_num += 1
if edge_num <= m and edge_num <= n:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
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)
exists_1 = False

for line in sys.stdin:
    a, b, c = list(map(int, line.split()))
    if c == 1:
        exists_1 = True
        continue
    uft.union(a, b)

cc = uft.connected_count()

min_m = n if exists_1 else n - 1
max_m = n - cc + cc * (cc - 1) // 2

print('Yes' if min_m <= m <= max_m else 'No')

Submission status: Wrong Answer

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

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

    # unite
    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

    # check
    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))
    # print(k, par_list)
    if k == 1:
        if m != n - 1:
            res = 'No'
    else:
        if m < n:
            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)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

    # unite
    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

    # check
    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'

    for i in range(n):
        _ = uf.find(i)

    k = len(set(uf.par))
    if k == 1:
        if m != n - 1:
            res = 'No'
    else:
        if m < n:
            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 _ in range(q):
        a, b, c = map(int, input().split())
        a_list.append(a)
        b_list.append(b)
        c_list.append(c)

    res = solve_d(n, m, q, a_list, b_list, c_list)
    print(res)


if __name__ == "__main__":
    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 len(AB1) == 0:
    if M == N-1:
        print('Yes')
else:
    if L >= 3:
        if S+L <= M <= S+L*(L-1)//2:
            print('Yes')
        else:
            print('No')
    else:
        if M == N-1:
            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 S+L <= M <= S+L*(L-1)//2:
        print('Yes')
    else:
        print('No')
else:
    if len(AB1) == 0 and M == N-1:
        print('No')
    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 >= 2:
    if S+L <= M <= S+L*(L-1)//2:
        print('Yes')
    else:
        print('No')
else:
    if M == N-1:
        print('Yes')
    else:
        print('No')

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 N-1+(PPP-2)*(PPP-1)//2 < M:
        flag = 1
            
    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 >= 2:
    if S+L <= M <= S+L*(L-1)//2:
        print('Yes')
    else:
        print('No')
else:
    if len(AB1) == 0 and M == N-1:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
class Union_Find():
    def __init__(self, num):
        self.par = [-1]*(num+1)
        self.siz = [1]*(num+1)

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

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

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.siz[ry] += self.siz[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
        return

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

zero = Union_Find(N)
one = Union_Find(N)
import sys
input = sys.stdin.readline
m = Q
for _ in range(Q):
    A, B, C = map(int, input().split())
    if C == 0:
        zero.union(A, B)
    else:
        one.union(A, B)



flag = 1
for i in range(N):
    if zero.size(i) != 1 and one.size(i) != 1:
        flag = 0

if flag == 1:
    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)

sizes = [0] * (N + 1)
for i in range(1, N + 1):
    sizes[UF.size(i)] += 1
num_g = 0
for i in range(1, N + 1):
    num_g += sizes[i] // i

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

if num_g - (two_num - two_num_new) < (two_num - two_num_new):
    print('No')
    sys.exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
class Union:
  def __init__(self, num):
    self.T = [-1 for i in range(num)]

  def root(self, x):
    if self.T[x] < 0: return x
    return self.root(self.T[x])

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

  def merge(self, x, y):
    a = self.root(x)
    b = self.root(y)
    if a == b: return False
    if self.size(a) < self.size(b): a, b = b, a
    self.T[a] += self.T[b]
    self.T[b] = a
    return True


N, M, Q = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for _ in range(Q)]

T = [1] * N

uni = Union(N)
L = []
for i in range(Q):
  a, b, c = ABC[i]
  T[a] = 0
  T[b] = 0
  if c == 0:
    uni.merge(a, b)
  else:
    L.append([a, b])
    
t = sum(T)
F = [0] * N
for x, y in L:
  if uni.merge(x, y) == False:
    t -= 2
    if t < 0:
      print("No")
      exit()
  else:
    t -= 1
    if t < 0:
      print("No")
      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 N-1+(PPP-2)*(PPP-1)//2 > M:
        flag = 1
            
    if flag == 0:
        print("Yes")
    else:
        print("No")
    
    
    
    
main()

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)

sizes = [0] * (N + 1)
for i in range(1, N + 1):
    sizes[UF.size(i)] += 1
num_g = 0
for i in range(1, N + 1):
    num_g += sizes[i] // i

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

if num_g - (two_num - two_num_new) < (two_num - two_num_new) * 2:
    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):
        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 == N-1:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
print('Yes')