Problem: 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.

Submission attempts (in order):
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")


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


Verdicts: Wrong Answer

Accepted