Problem:


Score : 800 points

Problem Statement

You are given a simple connected undirected graph consisting of N vertices and M edges.
The vertices are numbered 1 to N, and the edges are numbered 1 to M.

Edge i connects Vertex a_i and b_i bidirectionally.

Determine if three circuits (see Notes) can be formed using each of the edges exactly once.

Notes

A circuit is a cycle allowing repetitions of vertices but not edges.

Constraints

All values in input are integers.

1 \leq N,M \leq 10^{5}

1 \leq a_i, b_i \leq N

The given graph is simple and connected.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
:
a_M b_M

Output

If three circuits can be formed using each of the edges exactly once, print Yes; if they cannot, print No.

Sample Input 1

7 9
1 2
1 3
2 3
1 4
1 5
4 5
1 6
1 7
6 7

Sample Output 1

Yes

Three circuits can be formed using each of the edges exactly once, as follows:

Sample Input 2

3 3
1 2
2 3
3 1

Sample Output 2

No

Three circuits are needed.

Sample Input 3

18 27
17 7
12 15
18 17
13 18
13 6
5 7
7 1
14 5
15 11
7 6
1 9
5 4
18 16
4 6
7 2
7 11
6 3
12 14
5 2
10 5
7 8
10 15
3 15
9 8
7 15
5 16
18 15

Sample Output 3

Yes



Sample input:
7 9
1 2
1 3
2 3
1 4
1 5
4 5
1 6
1 7
6 7


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
p=[0]*n
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  p[a]+=1
  p[b]+=1
for i in p:
  if i%2:exit(print("No"))
if p.count(6)>=1 or p.count(4)>=4:print('Yes')
else:print('No')

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    #n = int(input())
    #l = list(map(int, input().split()))
    '''
    a=[]
    b=[]
    for i in range():
        A, B = map(int, input().split())
        a.append(A)
        b.append(B)'''

    n,m=map(int, input().split())
    l=[[]for _ in range(n)]
    cnt=0

    for i in range(m):
        A,B = map(int, input().split())
        A,B=A-1,B-1
        l[A].append(B)
        l[B].append(A)

    v4=[]
    for i in range(n):
        le=len(l[i])
        if le%2!=0:#euler
            print("No")
            sys.exit()

        if le>=4:
            cnt+=1
            v4.append(i)
    #e>6>4
    for item in v4:
        if len(l[item])>=6:
            print("Yes")
            sys.exit()

    if cnt<2:#4*1~0
        print("No")
        sys.exit()
    elif cnt>2:
        print("Yes")
        sys.exit()

    s,e=v4 #4*2
    for item in l[s]:
        p=s
        n=item

        while n!=p:
            for jtem in l[n]:
                if jtem!=p:
                    p,n=n,jtem
                    break
            
            if n==s:
                print("Yes")
                sys.exit()

    print("No")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    #n = int(input())
    #l = list(map(int, input().split()))
    '''
    a=[]
    b=[]
    for i in range():
        A, B = map(int, input().split())
        a.append(A)
        b.append(B)'''

    n,m=map(int, input().split())
    l=[[]for _ in range(n)]
    cnt=0

    for i in range(m):
        A, B = map(int, input().split())
        l[A-1].append(B-1)
        l[B-1].append(A-1)

    v4=[]
    for i in range(n):

        if len(l[i])%2!=0:#euler
            print("No")
            sys.exit()

        if len(l[i])>=4:
            cnt+=1
            v4.append(i)
    #e>6>4
    for item in v4:
        if len(l[item])>=6:
            print("Yes")
            sys.exit()

    if cnt<2:#4*1~0
        print("No")
        sys.exit()
    elif cnt>2:
        print("Yes")
        sys.exit()

    #v=[False for i in range(n)]
    s,e=v4 #4*2
    """
    n,m=map(int, input().split())
    l=[[]for _ in range(m)]
    for i in range(n):
        A, B = map(int, input().split())
        l[A-1].append(B-1)
        l[B-1].append(A-1)
    v=[False for i in range(n)]
    """
    for i in range(len(l[s])):
        p=s
        n=l[s][i]

        while n!=p:
            for j in range(len(l[n])):
                if l[n][j]!=p:
                    p,n=n,l[n][j]
                    break
            
            if n==s:
                print("Yes")
                sys.exit()

    print("No")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    #n = int(input())
    #l = list(map(int, input().split()))
    '''
    a=[]
    b=[]
    for i in range():
        A, B = map(int, input().split())
        a.append(A)
        b.append(B)'''

    n,m=map(int, input().split())
    l=[[]for _ in range(n)]
    cnt=0

    for i in range(m):
        A, B = map(int, input().split())
        l[A-1].append(B-1)
        l[B-1].append(A-1)

    v4=[]
    for i in range(n):

        if len(l[i])%2!=0:#euler
            print("No")
            sys.exit()

        if len(l[i])==4:
            cnt+=1
            v4.append(i)
    #6>4
    for item in v4:
        if len(l[item])>=6:
            print("Yes")
            sys.exit()

    if cnt<2:#4*1~0
        print("No")
        sys.exit()
    elif cnt>2:
        print("Yes")
        sys.exit()

    #v=[False for i in range(n)]
    s,e=v4 #4*2
    """
    n,m=map(int, input().split())
    l=[[]for _ in range(m)]
    for i in range(n):
        A, B = map(int, input().split())
        l[A-1].append(B-1)
        l[B-1].append(A-1)
    v=[False for i in range(n)]
    """
    for i in range(len(l[s])):
        p=s
        n=l[s][i]

        while n!=p:
            for j in range(len(l[n])):
                if l[n][j]!=p:
                    p,n=n,l[n][j]
                    break
            
            if n==s:
                print("Yes")
                sys.exit()

    print("No")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)'''

n,m=map(int, input().split())
l=[[]for _ in range(n)]
cnt=0

for i in range(m):
    A, B = map(int, input().split())
    l[A-1].append(B-1)
    l[B-1].append(A-1)
    if len(l[A-1])==6 or len(l[B-1])==6:
        print("Yes")
        sys.exit()

v4=[]
for i in range(n):

    if len(l[i])%2!=0:#euler
        print("No")
        sys.exit()

    if len(l[i])==4:
        cnt+=1
        if cnt==3:#4*3
            print("Yes")
            sys.exit()
        v4.append(i)

if cnt<2:#4*1~0
    print("No")
    sys.exit()

#v=[False for i in range(n)]
s,e=v4 #4*2
"""
n,m=map(int, input().split())
l=[[]for _ in range(m)]
for i in range(n):
    A, B = map(int, input().split())
    l[A-1].append(B-1)
    l[B-1].append(A-1)
v=[False for i in range(n)]
"""
for i in range(len(l[s])):
    p=s
    n=l[s][i]

    while n!=p:
        for j in range(len(l[n])):
            if l[n][j]!=p:
                p=n
                n=l[n][j]
                break
        
        if n==s:
            print("Yes")
            sys.exit()

print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)'''

n,m=map(int, input().split())
l=[[]for _ in range(n)]
cnt=0

for i in range(m):
    A, B = map(int, input().split())
    l[A-1].append(B-1)
    l[B-1].append(A-1)
    if len(l[A-1])==6 or len(l[B-1])==6:
        print("Yes")
        sys.exit()

v4=[]
for i in range(n):

    if len(l[i])%2!=0:#euler
        print("No")
        sys.exit()

    if len(l[i])==4:
        cnt+=1
        if cnt==3:#4*3
            print("Yes")
            sys.exit()
        v4.append(i)

if cnt<2:#4*1~0
    print("No")
    sys.exit()

#v=[False for i in range(n)]
s,e=v4 #4*2
"""
n,m=map(int, input().split())
l=[[]for _ in range(m)]
for i in range(n):
    A, B = map(int, input().split())
    l[A-1].append(B-1)
    l[B-1].append(A-1)
v=[False for i in range(n)]
"""
for i in range(len(l[s])):
    p=s
    n=l[s][i]

    while n!=p:
        for j in range(len(l[n])):
            if l[n][j]!=p:
                p,n=n,l[n][j]
                break
        
        if n==s:
            print("Yes")
            sys.exit()

print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
jdg = 0
for g in graph:
  if len(g)%2:
    print("No")
    exit()
  if len(g) == 4:
    jdg += 1
  elif len(g) >= 6:
    jdg += 3
if jdg >= 3:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
jdg = 0
for g in graph:
  if len(g)%2:
    print("No")
    exit()
  jdg += max(0,len(g)//2-1)
if jdg >= 2:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

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

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)


def solve():
    A = []
    for n in range(N):
        L = len(graph[n])
        if L % 2 != 0:
            return False
        if L > 2:
            A.append(n)

    for a in A:
        if len(graph[a]) > 4:
            return True
    if len(A) < 2:
        return False
    if len(A) > 2:
        return True
    
    s, t = A
    count = 0
    for sp in graph[s]:
        pre = s
        now = sp
        while now != t:
            for np in graph[now]:
                if np != pre:
                    pre = now
                    now = np
                    break
            if now == s:
                count += 1
                break
    return count < 4

print("Yes" if solve() else "No")

Submission status: Wrong Answer

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

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)


def solve():
    A = []
    for n in range(N):
        L = len(graph[n])
        if L % 2 != 0:
            return False
        if L > 2:
            A.append(L)

    for a in A:
        if a > 4:
            return True
    if len(A) < 2:
        return False
    if len(A) > 2:
        return True
    
    s, t = A
    for sp in graph[s]:
        pre = s
        now = sp
        while now != t:
            for np in graph[now]:
                if np != pre:
                    pre = now
                    now = np
                    break
            if now == s:
                return False
    return True

print("Yes" if solve() else "No")

Submission status: Wrong Answer

Solution code:
# AGC032C

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


def hoge():
    from collections import defaultdict
    n, m = map(int, input().split())

    ns = defaultdict(set)
    used = {}
    for _ in range(m):
        u,v = map(int, input().split())
        ns[u-1].add(v-1)
        ns[v-1].add(u-1)
        used[u-1,v-1] = False
        used[v-1,u-1] = False


    seen = [False] * n
    prev = [None] * n
    cs = []
    count = 0
    done = True
    
#     if not all(len(item)%2==0 and len(item)>0 for item in ns.values()):
#         print("No")
#         return


    for start in range(n):
        if seen[start]:
            continue
        q = [start]
        current_seen = [False] * n
        update = False
        while q:
            u = q.pop()
            current_seen[u] = True
            for v in ns[u]:
                if used[u,v] or prev[u]==v:
                    continue
                prev[v] = u
                if current_seen[v]:
                    # サイクル検出
                    count += 1
                    c = set()
                    tmp = v
                    while tmp not in c:
                        c.add(tmp)
                        used[tmp, prev[tmp]] = used[prev[tmp], tmp] = True
                        tmp = prev[tmp]
                    cs.append(c)
                    for u in c:
                        seen[u] = True
                    update = True
                    break
                q.append(v)
            if update:
                break
        if not update:
            print("No")
            return 

    def sub(cs):
        if len(cs)==1:
            return "No"
        elif len(cs)==2:
            if len(set(cs[0] & cs[1]))>=3:
                return "Yes"
            else:
                return "No"
        else :
            return "Yes"
    #     u2s = defaultdict(set)
    #     nns = defaultdict(set) # i番目のサイクルと重なるサイクル
    #     for i,s in enumerate(cs):
    #         for u in s:
    #             nns[i] |= u2s[u]
    #             u2s[u].add(i)
    #     for i,s in nns.items():
    #         for j in s:
    #             nns[j].add(i)
    #     count = 0
    # #     print(u2s)
    # #     print(nns)
    #     seen = [False] * len(cs)
    #     for start in range(len(cs)):
    #         if seen[start]:
    #             continue
    #         q = [start]
    #         seen[start] = True
    #         while q:
    #             u = q.pop()
    #             for v in nns[u]:
    #                 if not seen[v]:
    #                     q.append(v)
    #                     seen[v] = True
    #         count += 1
    #     if count<=3:
    #         return "Yes"
    #     else:
    #         return "No"
    if done:
        print(sub(cs))
    #     print("Yes")
hoge()

Submission status: Wrong Answer

Solution code:
# AGC032C

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
n, m = map(int, input().split())

ns = defaultdict(set)
used = {}
for _ in range(m):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    used[u-1,v-1] = False
    used[v-1,u-1] = False
    

seen = [False] * n
prev = [None] * n
cs = []
count = 0
done = True
for start in range(n):
    if seen[start]:
        continue
    q = [start]
    current_seen = [False] * n
    update = False
    while q:
#         print(q)
        u = q.pop()
        current_seen[u] = True
        for v in ns[u]:
            if used[u,v] or prev[u]==v:
                continue
            prev[v] = u
            if current_seen[v]:
                # サイクル検出
                count += 1
                c = set()
                tmp = v
                while tmp not in c:
                    c.add(tmp)
                    used[tmp, prev[tmp]] = used[prev[tmp], tmp] = True
                    tmp = prev[tmp]
                cs.append(c)
                for u in c:
                    seen[u] = True
                update = True
                break
            q.append(v)
        if update:
            break
    if not update:
        print("No")
        done = False
        break

def sub(cs):
    if len(cs)==1:
        return "No"
    elif len(cs)==2:
        if len(set(cs[0] & cs[1]))>=3:
            return "Yes"
        else:
            return "No"
    else :
        return "Yes"
#     u2s = defaultdict(set)
#     nns = defaultdict(set) # i番目のサイクルと重なるサイクル
#     for i,s in enumerate(cs):
#         for u in s:
#             nns[i] |= u2s[u]
#             u2s[u].add(i)
#     for i,s in nns.items():
#         for j in s:
#             nns[j].add(i)
#     count = 0
# #     print(u2s)
# #     print(nns)
#     seen = [False] * len(cs)
#     for start in range(len(cs)):
#         if seen[start]:
#             continue
#         q = [start]
#         seen[start] = True
#         while q:
#             u = q.pop()
#             for v in nns[u]:
#                 if not seen[v]:
#                     q.append(v)
#                     seen[v] = True
#         count += 1
#     if count<=3:
#         return "Yes"
#     else:
#         return "No"
if done:
    print(sub(cs))
#     print("Yes")

Submission status: Wrong Answer

Solution code:
# AGC032C

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
n, m = map(int, input().split())

ns = defaultdict(set)
used = {}
for _ in range(m):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    used[u-1,v-1] = False
    used[v-1,u-1] = False
    

seen = [False] * n
prev = [None] * n
cs = []
count = 0
done = True
for start in range(n):
    if seen[start]:
        continue
    q = [start]
    current_seen = [False] * n
    update = False
    while q:
#         print(q)
        u = q.pop()
        current_seen[u] = True
        for v in ns[u]:
            if used[u,v] or prev[u]==v:
                continue
            prev[v] = u
            if current_seen[v]:
                # サイクル検出
                count += 1
                c = set()
                tmp = v
                while tmp not in c:
                    c.add(tmp)
                    used[tmp, prev[tmp]] = used[prev[tmp], tmp] = True
                    tmp = prev[tmp]
                cs.append(c)
                for u in c:
                    seen[u] = True
                update = True
                break
            q.append(v)
        if update:
            break
    if not update:
        print("No")
        done = False
        break

def sub(cs):
    if len(cs)<=2:
        return "No"
    else :
        return "Yes"
#     u2s = defaultdict(set)
#     nns = defaultdict(set) # i番目のサイクルと重なるサイクル
#     for i,s in enumerate(cs):
#         for u in s:
#             nns[i] |= u2s[u]
#             u2s[u].add(i)
#     for i,s in nns.items():
#         for j in s:
#             nns[j].add(i)
#     count = 0
# #     print(u2s)
# #     print(nns)
#     seen = [False] * len(cs)
#     for start in range(len(cs)):
#         if seen[start]:
#             continue
#         q = [start]
#         seen[start] = True
#         while q:
#             u = q.pop()
#             for v in nns[u]:
#                 if not seen[v]:
#                     q.append(v)
#                     seen[v] = True
#         count += 1
#     if count<=3:
#         return "Yes"
#     else:
#         return "No"
if done:
    print(sub(cs))
#     print("Yes")

Submission status: Wrong Answer

Solution code:
# AGC032C

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
n, m = map(int, input().split())

ns = defaultdict(set)
used = {}
for _ in range(m):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    used[u-1,v-1] = False
    used[v-1,u-1] = False
    

seen = [False] * n
prev = [None] * n
cs = []
count = 0
done = True
for start in range(n):
    if seen[start]:
        continue
    q = [start]
    current_seen = [False] * n
    update = False
    while q:
#         print(q)
        u = q.pop()
        current_seen[u] = True
        for v in ns[u]:
            if used[u,v] or prev[u]==v:
                continue
            prev[v] = u
            if current_seen[v]:
                # サイクル検出
                count += 1
                c = set()
                tmp = v
                while tmp not in c:
                    c.add(tmp)
                    used[tmp, prev[tmp]] = used[prev[tmp], tmp] = True
                    tmp = prev[tmp]
                cs.append(c)
                for u in c:
                    seen[u] = True
                update = True
                break
            q.append(v)
        if update:
            break
    if not update:
        print("No")
        done = False
        break

def sub(cs):
    if len(cs)<=2:
        return "No"
    elif len(cs)==3:
        return "Yes"
    u2s = defaultdict(set)
    nns = defaultdict(set) # i番目のサイクルと重なるサイクル
    for i,s in enumerate(cs):
        for u in s:
            nns[i] |= u2s[u]
            u2s[u].add(i)
    for i,s in nns.items():
        for j in s:
            nns[j].add(i)
    count = 0
#     print(u2s)
#     print(nns)
    seen = [False] * len(cs)
    for start in range(len(cs)):
        if seen[start]:
            continue
        q = [start]
        seen[start] = True
        while q:
            u = q.pop()
            for v in nns[u]:
                if not seen[v]:
                    q.append(v)
                    seen[v] = True
        count += 1
    if count<=3:
        return "Yes"
    else:
        return "No"
if done:
    print(sub(cs))
#     print("Yes")

Submission status: Wrong Answer

Solution code:
# AGC032C

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
n, m = map(int, input().split())

ns = defaultdict(set)
used = {}
for _ in range(m):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    used[u-1,v-1] = False
    used[v-1,u-1] = False
    

seen = [False] * n
prev = [None] * n
cs = []
count = 0
done = True
for start in range(n):
    if seen[start]:
        continue
    q = [start]
    current_seen = [False] * n
    update = False
    while q:
#         print(q)
        u = q.pop()
        current_seen[u] = True
        for v in ns[u]:
            if used[u,v] or prev[u]==v:
                continue
            prev[v] = u
            if current_seen[v]:
                # サイクル検出
                count += 1
                c = set()
                tmp = v
                while tmp not in c:
                    c.add(tmp)
                    used[tmp, prev[tmp]] = used[prev[tmp], tmp] = True
                    tmp = prev[tmp]
                cs.append(c)
                for u in c:
                    seen[u] = True
                update = True
                break
            q.append(v)
        if update:
            break
    if not update:
        print("No")
        done = False
        break

def sub(cs):
    if len(cs)<=2:
        return "No"
    elif len(cs)==3:
        return "Yes"
    u2s = defaultdict(set)
    nns = defaultdict(set) # i番目のサイクルと重なるサイクル
    for i,s in enumerate(cs):
        for u in s:
            nns[i] |= u2s[u]
            u2s[u].add(i)
    for i,s in nns.items():
        for j in s:
            nns[j].add(i)
    count = 0
#     print(u2s)
#     print(nns)
    seen = [False] * len(cs)
    for start in range(len(cs) - 1, -1, -1):
        if seen[start]:
            continue
        q = [start]
        seen[start] = True
        while q:
            u = q.pop()
            for v in nns[u]:
                if not seen[v]:
                    q.append(v)
                    seen[v] = True
        count += 1
    if count<=3:
        return "Yes"
    else:
        return "No"
if done:
    print(sub(cs))
#     print("Yes")

Submission status: Wrong Answer

Solution code:
# AGC032C

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
n, m = map(int, input().split())

ns = defaultdict(set)
used = {}
for _ in range(m):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    used[u-1,v-1] = False
    used[v-1,u-1] = False
    

seen = [False] * n
prev = [None] * n
cs = []
count = 0
done = True
for start in range(n):
    if seen[start]:
        continue
    q = [start]
    current_seen = [False] * n
    update = False
    while q:
#         print(q)
        u = q.pop()
        current_seen[u] = True
        for v in ns[u]:
            if used[u,v] or prev[u]==v:
                continue
            prev[v] = u
            if current_seen[v]:
                # サイクル検出
                count += 1
                c = set()
                tmp = v
                while tmp not in c:
                    c.add(tmp)
                    used[tmp, prev[tmp]] = used[prev[tmp], tmp] = True
                    tmp = prev[tmp]
                cs.append(c)
                for u in c:
                    seen[u] = True
                update = True
                break
            q.append(v)
        if update:
            break
    if not update:
        print("No")
        done = False
        break

def sub(cs):
    if len(cs)<=2:
        return "No"
    elif len(cs)==3:
        return "Yes"
    u2s = defaultdict(set)
    nns = defaultdict(set) # i番目のサイクルと重なるサイクル
    for i,s in enumerate(cs):
        for u in s:
            nns[i] |= u2s[u]
            u2s[u].add(i)
    count = 0
    seen = [False] * len(cs)
    for start in range(len(cs) - 1, -1, -1):
        if seen[start]:
            continue
        q = [start]
        seen[start] = True
        while q:
            u = q.pop()
            for v in nns[u]:
                if not seen[v]:
                    q.append(v)
                    seen[v] = True
        count += 1
    if count<=3:
        return "Yes"
    else:
        return "No"
if done:
    print(sub(cs))
#     print("Yes")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
G = [set() for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a - 1].add(b - 1)
    G[b - 1].add(a - 1)

ret = 0
for i in range(n):
    if len(G[i]) % 2:
        print('No')
        exit()
    ret += len(G[i]) // 2 - 1
    if ret >= 2:
        print('Yes')
        break
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

cnt4 = 0
cnt6 = 0
for i in range(n):
    if len(graph[i]) % 2 == 1:
        print("No")
        exit()
    elif len(graph[i]) == 4:
        cnt4 += 1
    elif len(graph[i]) >= 6:
        cnt6 += 1

def solve():
    v4 = []
    for i in range(n):
        if len(graph[i]) == 4:
            v4.append(i)

    v0 = v4[0]
    v1 = v4[1]
    
    used = [False] * n
    used[v0] = True
    stack = [(v0, -1)]
    while stack:
        v, prv_v = stack.pop()
        for nxt_v in graph[v]:
            if prv_v == nxt_v:
                continue
            if nxt_v == v0:
                return True
            if used[nxt_v]:
                continue
            used[nxt_v] = True
            stack.append((nxt_v, v))
    return False

if cnt6 >= 1:
    print("Yes")
elif cnt4 >= 3:
    print("Yes")
elif cnt4 == 2:
    if solve():
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

cnt4 = 0
cnt6 = 0
for i in range(n):
    if len(graph[i]) % 2 == 1:
        print("No")
        exit()
    elif len(graph[i]) == 4:
        cnt4 += 1
    elif len(graph[i]) >= 6:
        cnt6 += 1

if cnt6 >= 1 or cnt4 >= 2:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

cnt4 = 0
cnt6 = 0
for i in range(n):
    if len(graph[i]) % 2 == 1:
        print("No")
        exit()
    elif len(graph[i]) == 4:
        cnt4 += 1
    elif len(graph[i]) >= 6:
        cnt6 += 1

if cnt6 >= 1 or cnt4 >= 2:
    print("Yes")

Submission status: Wrong Answer

Solution code:
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
G = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    cnt[a-1]+=1
    cnt[b-1]+=1
if any(cnt[i]%2 == 1 for i in range(n)):
    print('No')
    sys.exit()
c = cnt.count(4)
if any(cnt[i]>=6 for i in range(n)) or c>=3:
    print('Yes')
    sys.exit()
if c<1:
    print('No')
    sys.exit()
v = cnt.index(4)
for v0 in G[v]:
    now = v0
    p = v
    while True:
        for nv in G[now]:
            if nv == p:
                continue
            p = now
            now = nv
            break
        if now == v:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
G = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    cnt[a-1]+=1
    cnt[b-1]+=1
if any(cnt[i]%2 == 1 for i in range(n)):
    print('No')
    sys.exit()
c = cnt.count(4)
if any(cnt[i]>=6 for i in range(n)) or c>=3:
    print('Yes')
    sys.exit()
if c<1:
    print('No')
    sys.exit()
v = cnt.index(4)
for v0 in G[v]:
    used = [False]*n
    now = v0
    used[v0] = True
    while True:
        for nv in G[now]:
            if used[nv]:
                continue
            now = nv
            used[now] = True
            break
        if now == v0:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
G = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    cnt[a-1]+=1
    cnt[b-1]+=1
if any(cnt[i]%2 == 1 for i in range(n)):
    print('No')
    sys.exit()
c = cnt.count(4)
if any(cnt[i]>=6 for i in range(n)) or c>=3:
    print('Yes')
    sys.exit()
if c<1:
    print('No')
    sys.exit()
v = cnt.index(4)
for v0 in G[v]:
    used = [False]*n
    now = v0
    used[v0] = True
    while True:
        for nv in G[now]:
            if used[nv]:
                continue
            now = nv
            break
            used[now] = True
        if now == v0:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')