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:
#! /usr/bin/env python3

### @file up.py
### @brief
### @author Yusuke Matsunaga (松永 裕介)
###
### Copyright (C) 2019 Yusuke Matsunaga
### All rights reserved.

n_str, m_str, q_str = input().split()
N = int(n_str)
M = int(m_str)
Q = int(q_str)

# 隣接リスト
adj_list = [ [] for i in range(N) ]

# multi path のペアを作る．
multi_pair = []
for i in range(Q) :
    a_str, b_str, c_str = input().split()
    a = int(a_str)
    b = int(b_str)
    c = int(c_str)
    assert 0 <= a < N
    assert 0 <= b < N
    assert c == 0 or c == 1
    # 正規化しておく
    if b < a :
        tmp = a
        a = b
        b = tmp
    if c :
        # multi path
        multi_pair.append( (a, b) )
    else :
        # single path
        adj_list[a].append(b)
        adj_list[b].append(a)


# 特別なケース
if M == N - 1 and len(multi_pair) > 0 :
    # M = N - 1 は木構造しかありえない．
    print('No')
    exit(0)

# グループ番号
group_id = [ -1 for i in range(N) ]

def dfs(i, gid) :
    if i < 0 or i >= N :
        return
    if group_id[i] != -1 :
        # 処理済み
        #assert group_id[i] == gid
        return

    group_id[i] = gid
    print('{} => Group#{}'.format(i, gid))
    for j in adj_list[i] :
        #dfs(j, gid)
        pass

gid = 0
for i in range(N) :
    if group_id[i] == -1 :
       group_id[i] = gid
       print('{} => Group#{}'.format(i, gid))
       for j in adj_list[i] :
           dfs(j, gid)
       gid += 1


# チェック1
# 同一の single path グループ内で multi path 制約がある．
for a, b in multi_pair :
    rep_a = group_id[a]
    rep_b = group_id[b]
    if rep_a == rep_b :
        print('No')
        exit(0)

K = gid
if K == 2 :
    K = 1

#print('k = {}'.format(k))
#print('n = {}, m = {}'.format(n, m))
#print('n + k * (k - 3) / 2 = {}'.format(n + k * (k - 3) // 2))

if M <= N + K * (K - 3) // 2 :
    print('Yes')
else :
    print('No')

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3

### @file up.py
### @brief
### @author Yusuke Matsunaga (松永 裕介)
###
### Copyright (C) 2019 Yusuke Matsunaga
### All rights reserved.

n_str, m_str, q_str = input().split()
N = int(n_str)
M = int(m_str)
Q = int(q_str)

# 隣接リスト
adj_list = [ [] for i in range(N) ]

# multi path のペアを作る．
multi_pair = []
for i in range(Q) :
    a_str, b_str, c_str = input().split()
    a = int(a_str)
    b = int(b_str)
    c = int(c_str)
    assert 0 <= a < N
    assert 0 <= b < N
    assert c == 0 or c == 1
    # 正規化しておく
    if b < a :
        tmp = a
        a = b
        b = tmp
    if c :
        # multi path
        multi_pair.append( (a, b) )
    else :
        # single path
        adj_list[a].append(b)
        adj_list[b].append(a)


# 特別なケース
if M == N - 1 and len(multi_pair) > 0 :
    # M = N - 1 は木構造しかありえない．
    print('No')
    exit(0)

# グループ番号
group_id = [ -1 for i in range(N) ]

def dfs(i, gid) :
    if group_id[i] != -1 :
        # 処理済み
        #assert group_id[i] == gid
        return

    group_id[i] = gid
    #for j in adj_list[i] :
    #    dfs(j, gid)

gid = 0
for i in range(N) :
    if group_id[i] == -1 :
       group_id[i] = gid
       for j in adj_list[i] :
           dfs(j, gid)
       gid += 1

exit(0)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3

### @file up.py
### @brief
### @author Yusuke Matsunaga (松永 裕介)
###
### Copyright (C) 2019 Yusuke Matsunaga
### All rights reserved.

n_str, m_str, q_str = input().split()
n = int(n_str)
m = int(m_str)
q = int(q_str)

# single path と multi path のペアを作る．
single_pair = []
multi_pair = []
for i in range(q) :
    a_str, b_str, c_str = input().split()
    a = int(a_str)
    b = int(b_str)
    c = int(c_str)
    assert 0 <= a < n
    assert 0 <= b < n
    assert c == 0 or c == 1
    # 正規化しておく
    if b < a :
        tmp = a
        a = b
        b = tmp
    if c :
        # multi path
        multi_pair.append( (a, b) )
    else :
        # single path
        single_pair.append( (a, b) )


# 特別なケース
if m == n - 1 and len(multi_pair) > 0 :
    # M = N - 1 は木構造しかありえない．
    print('No')
    exit(0)

# single path のグループを作る．
adj_list = [ [] for i in range(n) ]
for a, b in single_pair :
    adj_list[a].append(b)
    adj_list[b].append(a)

group_id = [ -1 for i in range(n) ]

def dfs(i, gid) :
    if group_id[i] != -1 :
        # 処理済み
        #assert group_id[i] == gid
        return

    group_id[i] = gid
    for j in adj_list[i] :
        dfs(j, gid)

for i in range(n) :
    for j in adj_list[i] :
        assert 0 <= j and j < n

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3

### @file up.py
### @brief
### @author Yusuke Matsunaga (松永 裕介)
###
### Copyright (C) 2019 Yusuke Matsunaga
### All rights reserved.

n_str, m_str, q_str = input().split()
n = int(n_str)
m = int(m_str)
q = int(q_str)

# single path と multi path のペアを作る．
single_pair = []
multi_pair = []
for i in range(q) :
    a_str, b_str, c_str = input().split()
    a = int(a_str)
    b = int(b_str)
    c = int(c_str)
    assert 0 <= a < n
    assert 0 <= b < n
    assert c == 0 or c == 1
    # 正規化しておく
    if b < a :
        tmp = a
        a = b
        b = tmp
    if c :
        # multi path
        multi_pair.append( (a, b) )
    else :
        # single path
        single_pair.append( (a, b) )


# 特別なケース
if m == n - 1 and len(multi_pair) > 0 :
    # M = N - 1 は木構造しかありえない．
    print('No')
    exit(0)

# single path のグループを作る．
adj_list = [ [] for i in range(n) ]
for a, b in single_pair :
    adj_list[a].append(b)
    adj_list[b].append(a)

group_id = [ -1 for i in range(n) ]

def dfs(i, gid) :
    if group_id[i] != -1 :
        # 処理済み
        #assert group_id[i] == gid
        return

    group_id[i] = gid
    for j in adj_list[i] :
        pass
    #    dfs(j, gid)

gid = 0
for i in range(n) :
    if group_id[i] == -1 :
       group_id[i] = gid
       for j in adj_list[i] :
           dfs(j, gid)
       gid += 1

exit(0)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3

### @file up.py
### @brief
### @author Yusuke Matsunaga (松永 裕介)
###
### Copyright (C) 2019 Yusuke Matsunaga
### All rights reserved.

n_str, m_str, q_str = input().split()
n = int(n_str)
m = int(m_str)
q = int(q_str)

# single path と multi path のペアを作る．
single_pair = []
multi_pair = []
for i in range(q) :
    a_str, b_str, c_str = input().split()
    a = int(a_str)
    b = int(b_str)
    c = int(c_str)
    assert 0 <= a < n
    assert 0 <= b < n
    assert c == 0 or c == 1
    # 正規化しておく
    if b < a :
        tmp = a
        a = b
        b = tmp
    if c :
        # multi path
        multi_pair.append( (a, b) )
    else :
        # single path
        single_pair.append( (a, b) )


# 特別なケース
if m == n - 1 and len(multi_pair) > 0 :
    # M = N - 1 は木構造しかありえない．
    print('No')
    exit(0)

# single path のグループを作る．
adj_list = [ [] for i in range(n) ]
for a, b in single_pair :
    adj_list[a].append(b)
    adj_list[b].append(a)

group_id = [ -1 for i in range(n) ]

def dfs(i, gid) :
    if group_id[i] != -1 :
        # 処理済み
        #assert group_id[i] == gid
        return

    group_id[i] = gid
    #for j in adj_list[i] :
    #    dfs(j, gid)

gid = 0
for i in range(n) :
    if group_id[i] == -1 :
       group_id[i] = gid
       for j in adj_list[i] :
           dfs(j, gid)
       gid += 1

exit(0)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3

### @file up.py
### @brief
### @author Yusuke Matsunaga (松永 裕介)
###
### Copyright (C) 2019 Yusuke Matsunaga
### All rights reserved.

n_str, m_str, q_str = input().split()
n = int(n_str)
m = int(m_str)
q = int(q_str)

# single path と multi path のペアを作る．
single_pair = []
multi_pair = []
for i in range(q) :
    a_str, b_str, c_str = input().split()
    a = int(a_str)
    b = int(b_str)
    c = int(c_str)
    assert 0 <= a < n
    assert 0 <= b < n
    assert c == 0 or c == 1
    # 正規化しておく
    if b < a :
        tmp = a
        a = b
        b = tmp
    if c :
        # multi path
        multi_pair.append( (a, b) )
    else :
        # single path
        single_pair.append( (a, b) )


# 特別なケース
if m == n - 1 and len(multi_pair) > 0 :
    # M = N - 1 は木構造しかありえない．
    print('No')
    exit(0)

# single path のグループを作る．
adj_list = [ [] for i in range(n) ]
for a, b in single_pair :
    adj_list[a].append(b)
    adj_list[b].append(a)

group_id = [ -1 for i in range(n) ]

exit(0)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3

### @file up.py
### @brief
### @author Yusuke Matsunaga (松永 裕介)
###
### Copyright (C) 2019 Yusuke Matsunaga
### All rights reserved.

n_str, m_str, q_str = input().split()
n = int(n_str)
m = int(m_str)
q = int(q_str)

# single path と multi path のペアを作る．
single_pair = []
multi_pair = []
for i in range(q) :
    a_str, b_str, c_str = input().split()
    a = int(a_str)
    b = int(b_str)
    c = int(c_str)
    assert 0 <= a < n
    assert 0 <= b < n
    assert c == 0 or c == 1
    # 正規化しておく
    if b < a :
        tmp = a
        a = b
        b = tmp
    if c :
        # multi path
        multi_pair.append( (a, b) )
    else :
        # single path
        single_pair.append( (a, b) )

exit(0)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3

### @file up.py
### @brief
### @author Yusuke Matsunaga (松永 裕介)
###
### Copyright (C) 2019 Yusuke Matsunaga
### All rights reserved.

n_str, m_str, q_str = input().split()
n = int(n_str)
m = int(m_str)
q = int(q_str)

# single path と multi path のペアを作る．
single_pair = []
multi_pair = []
for i in range(q) :
    a_str, b_str, c_str = input().split()
    a = int(a_str)
    b = int(b_str)
    c = int(c_str)
    # 正規化しておく
    if b < a :
        tmp = a
        a = b
        b = tmp
    if c :
        # multi path
        multi_pair.append( (a, b) )
    else :
        # single path
        single_pair.append( (a, b) )

# single path のグループを作る．
rep_list = [ -1 for i in range(n) ]
for a, b in single_pair :
    if rep_list[a] == -1 :
        rep_list[a] = a
    if rep_list[b] == -1 :
        rep_list[b] = b
    if rep_list[a] < rep_list[b] :
        rep_list[b] = rep_list[a]
    else :
        rep_list[a] = rep_list[b]

# 愚直なアルゴリズム
while True :
    changed = False
    for a, b in single_pair :
        if rep_list[a] < rep_list[b] :
            rep_list[b] = rep_list[a]
            changed = True
        elif rep_list[b] < rep_list[a] :
            rep_list[a] = rep_list[b]
            changed = True
    if not changed :
        break

# 以降，ノード番号はすべて代表番号で考える．
ng = 0
ns = 0
group_top = []
for i in range(n) :
    if rep_list[i] == -1 :
        continue
    if rep_list[i] == i :
        # 代表ノード
        ng += 1
        group_top.append(i)
    ns += 1

#for top in group_top :
#    for i in range(n) :
#        if rep_list[i] == top :
#            print(' {}'.format(i), end = '')
#    print()

# チェック1
# 同一の single path グループ内で multi path 制約がある．
for a, b in multi_pair :
    rep_a = rep_list[a]
    rep_b = rep_list[b]
    if rep_a != -1 and rep_a == rep_b :
        print('No')
        exit(0)

# チェック2
nr = 0
for i in range(n) :
    if rep_list[i] == -1 :
        nr += 1

#print('ng = {}, nr = {}'.format(ng, nr))
k = ng + nr
if k < 3 :
    print('No')
    exit(0)
#print('k = {}'.format(k))
#print('n = {}, m = {}'.format(n, m))
#print('n + k * (k - 3) / 2 = {}'.format(n + k * (k - 3) // 2))

if m <= n + k * (k - 3) // 2 :
    print('Yes')
else :
    print('No')

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3

### @file up.py
### @brief
### @author Yusuke Matsunaga (松永 裕介)
###
### Copyright (C) 2019 Yusuke Matsunaga
### All rights reserved.

n_str, m_str, q_str = input().split()
n = int(n_str)
m = int(m_str)
q = int(q_str)

# single path と multi path のペアを作る．
single_pair = []
multi_pair = []
for i in range(q) :
    a_str, b_str, c_str = input().split()
    a = int(a_str)
    b = int(b_str)
    c = int(c_str)
    # 正規化しておく
    if b < a :
        tmp = a
        a = b
        b = tmp
    if c :
        # multi path
        multi_pair.append( (a, b) )
    else :
        # single path
        single_pair.append( (a, b) )

# single path のグループを作る．
rep_list = [ -1 for i in range(n) ]
for a, b in single_pair :
    if rep_list[a] == -1 :
        rep_list[a] = a
    if rep_list[b] == -1 :
        rep_list[b] = b
    if rep_list[a] < rep_list[b] :
        rep_list[b] = rep_list[a]
    else :
        rep_list[a] = rep_list[b]

# 愚直なアルゴリズム
while True :
    changed = False
    for a, b in single_pair :
        if rep_list[a] < rep_list[b] :
            rep_list[b] = rep_list[a]
            changed = True
        elif rep_list[b] < rep_list[a] :
            rep_list[a] = rep_list[b]
            changed = True
    if not changed :
        break

# 以降，ノード番号はすべて代表番号で考える．
ng = 0
ns = 0
group_top = []
for i in range(n) :
    if rep_list[i] == -1 :
        continue
    if rep_list[i] == i :
        # 代表ノード
        ng += 1
        group_top.append(i)
    ns += 1

#for top in group_top :
#    for i in range(n) :
#        if rep_list[i] == top :
#            print(' {}'.format(i), end = '')
#    print()

# チェック1
# 同一の single path グループ内で multi path 制約がある．
for a, b in multi_pair :
    rep_a = rep_list[a]
    rep_b = rep_list[b]
    if rep_a != -1 and rep_a == rep_b :
        print('No')
        exit(0)

# チェック2
nr = 0
for i in range(n) :
    if rep_list[i] == -1 :
        nr += 1

#print('ng = {}, nr = {}'.format(ng, nr))
k = ng + nr
if k < 3 :
    print('NO')
    exit(0)
#print('k = {}'.format(k))
#print('n = {}, m = {}'.format(n, m))
#print('n + k * (k - 3) / 2 = {}'.format(n + k * (k - 3) // 2))

if m <= n + k * (k - 3) // 2 :
    print('Yes')
else :
    print('NO')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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))
    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
    print(b, (counter)*(counter-1)//2)
    if M<=b+((counter)*(counter-1)//2):
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

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))
    for e in es:
        if node_list[e[0]].root() == node_list[e[1]].root():
            print("No")
            sys.exit()
    counter = 0
    for node in node_list:
        if node.root().member_num_ != 1:
            counter += 1
    if M<=(N-counter)+((counter)*(counter-1)//2):
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
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:
        # loop with simple path
        if Forest.same_check(a, b):
            print("No")
            exit()
        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:
    # multipath in tree
    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")

Submission status: Wrong Answer

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

for a, b, c in circles:
    # multipath in tree
    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")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
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_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)
        group_num -= 1
        edge_num += 1
    else:
        circles.append((a, b, c))

for a, b, c in circles:
    # multipath in tree
    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")

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 find_group(self, x):
        if self.group[x] == x:
            return x
        else:
            self.group[x] = self.find_group(self.group[x])
            return self.group[x]

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

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

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

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 += 2
if edge_num <= m:
    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 find_group(self, x):
        if self.group[x] == x:
            return x
        else:
            self.group[x] = self.find_group(self.group[x])
            return self.group[x]

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

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

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