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: Accepted

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 not Forest.same_check(a, b):
            Forest.union(a, b)
            group_num -= 1
            edge_num += 1
    else:
        circles.append((a, b, c))
    seen.add((a, b, c))

for a, b, c in circles:
    # 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: Accepted

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 not Forest.same_check(a, b):
            Forest.union(a, b)
            group_num -= 1
            edge_num += 1
    else:
        circles.append((a, b, c))
    seen.add((a, b, c))

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

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

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

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

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

C=len(set(Group))

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

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


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

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

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

            return True
        return False

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

def main():
    n,m,q = LI()
    aa = [LI() for _ in range(q)]
    uf = UnionFind(n)
    t = 0
    cc = 0
    for a,b,c in aa:
        if c == 0:
            if uf.union(a,b):
                t += 1
        else:
            cc += 1

    for a,b,c in aa:
        if c == 0:
            continue
        if uf.find(a) == uf.find(b):
            return 'No'

    if m == n - 1:
        if cc == 0:
            return 'Yes'
        return 'No'

    if m <= n - uf.l + uf.l * (uf.l-1) // 2:
        return 'Yes'

    return 'No'


print(main())

Submission status: Accepted

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)
hyper_paths = set()

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

for a, b in hyper_paths:
    if uft.find(a, b):
        print('No')
        exit()

cc = uft.connected_count()

min_m = n if len(hyper_paths) > 0 else n - 1
max_m = n - cc + cc * (cc - 1) // 2

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

Submission status: Accepted

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 max(c_list) == 0:
        min_m = n - 1
    else:
        min_m = n
    if m < min_m:
        res = 'No'
    elif m > n + k * (k - 3) // 2:
        res = 'No'

    return res


def main():
    n, m, q = map(int, input().split())
    a_list = [0] * q
    b_list = [0] * q
    c_list = [0] * q

    for i in range(q):
        a, b, c = map(int, input().split())
        a_list[i] = a
        b_list[i] = b
        c_list[i] = c

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.rank=[0]*n
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
    def same_check(self,x,y):
        return self.find(x)==self.find(y)

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

if __name__=='__main__':
    main()

Submission status: Accepted

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
        elif M == N-1:
            flag = 1
            break
    
    if N-1+((PPP-2)*(PPP-1))//2 < M:
        flag = 1
            
    if flag == 0:
        print("Yes")
    else:
        print("No")
    
    
    
    
main()

Submission status: Runtime Error

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)


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: Runtime Error

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: Runtime Error

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)

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: Runtime Error

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
    print('{} => Group#{}'.format(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
       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: Runtime Error

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: Runtime Error

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: Runtime Error

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: Runtime Error

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_listi] :
        assert 0 <= j < n

Submission status: Runtime Error

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: Runtime Error

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: Runtime Error

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)