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:
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:
        print(now)
        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')

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)
used = [False]*n
for v0 in G[v]:
    now = v0
    used[v0] = True
    for i in range(n):
        for nv in G[now]:
            if used[nv]:
                continue
            now = nv
            used[now] = True
        if now == v0:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, M = map(int, input().split())
adjL = [[] for _ in range(N)]
degs = [0] * N
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    adjL[a].append(b)
    adjL[b].append(a)
    degs[a] += 1
    degs[b] += 1

cnt = Counter(degs)

if any([key%2 for key in cnt.keys()]):
    print('No')
else:
    cnt[2] = 0
    if sum(cnt.values()) >= 4 or max(cnt.keys()) >= 6:
        print('Yes')
    elif cnt[4] < 2:
        print('No')
    else:
        useds = [False] * N
        vs = []
        for v in range(N):
            if degs[v] == 4:
                useds[v] == True
                vs.append(v)
        for v2 in adjL[vs[0]]:
            v, vPar = v2, vs[0]
            while not useds[v]:
                useds[v] = True
                for v2 in adjL[v]:
                    if v2 != vPar:
                        vPar = v
                        v = v2
                        break
        if all(useds):
            print('No')
        else:
            print('Yes')

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, M = map(int, input().split())
adjL = [[] for _ in range(N)]
degs = [0] * N
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    adjL[a].append(b)
    adjL[b].append(a)
    degs[a] += 1
    degs[b] += 1

cnt = Counter(degs)

if any([key%2 for key in cnt.keys()]):
    print('No')
else:
    del cnt[2]
    if cnt == Counter():
        print('No')
    elif cnt != Counter([4, 4]):
        print('Yes')
    else:
        useds = [False] * N
        vs = []
        for v in range(N):
            if degs[v] == 4:
                useds[v] == True
                vs.append(v)
        for v2 in adjL[vs[0]]:
            v, vPar = v2, v
            while not useds[v]:
                useds[v] = True
                for v2 in adjL[v]:
                    if v2 != vPar:
                        vPar = v
                        v = v2
                        break
        if all(useds):
            print('No')
        else:
            print('Yes')

Submission status: Wrong Answer

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

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

deg = [len(A) for A in adj]
f = []
for i in range(1, N+1):
    if deg[i] % 2 == 1:
        print('No')
        exit()
    elif deg[i] >= 6:
        print('Yes')
        exit()
    elif deg[i] == 4:
        f.append(i)

if len(f) >= 3:
    print('Yes')
    exit()

if len(f) <= 1:
    print('No')
    exit()

t1, t2 = f[0], f[1]
seen = [0] * (N+1)
seen[t1] = 1
seen[t2] = 1
st = [t1]
while st:
    v = st.pop()
    for u in adj[v]:
        if seen[u] == 0:
            seen[u] = 1
            st.append(u)

if sum(seen) != N:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

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

deg = [len(A) for A in adj]
f = []
for i in range(1, N+1):
    if deg[i] % 2 == 1:
        print('No')
        exit()
    elif deg[i] >= 6:
        print('Yes')
        exit()
    elif deg[i] == 4:
        f.append(i)

if len(f) >= 3:
    print('Yes')
    exit()

if len(f) <= 1:
    print('No')
    exit()

t1, t2 = f[0], f[1]
seen = [0] * (N+1)
seen[t1] = 1
seen[t2] = 1
st = [t1]
while st:
    v = st.pop()
    for u in adj[v]:
        if seen[u] == 0:
            seen[u] = 1
            st.append(u)
        else:
            if u in adj[t1] and u != t2:
                print('Yes')
                exit()

print('No')

Submission status: Wrong Answer

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

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

deg = [len(A) for A in adj]
f = []
for i in range(1, N+1):
    if deg[i] % 2 == 1:
        print('No')
        exit()
    elif deg[i] >= 6:
        print('Yes')
        exit()
    elif deg[i] == 4:
        f.append(i)

if len(f) >= 3:
    print('Yes')
    exit()

if len(f) <= 1:
    print('No')
    exit()

t1, t2 = f[0], f[1]
seen = [0] * (N+1)
seen[t1] = 1
seen[t2] = 1
s1 = adj[t1]
for s in s1:
    st = [s]
    seen[s] = 1
    while st:
        v = st.pop()
        for u in adj[v]:
            if seen[u] == 0:
                if u in s1:
                    print('Yes')
                    exit()
                seen[u] = 1
                st.append(u)

print('No')

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
N, M = map(int, readline().split())

def check(Edge, Dim):
    N = len(Edge)
    if any(d&1 for d in Dim):
        return 'No'
    if max(Dim) > 4:
        return 'Yes'
    dc4 = Dim.count(4)
    if dc4 <= 1:
        return 'No'
    if dc4 >= 3:
        return 'Yes'
    a = Dim.index(4)
    st = (a+1)%N
    used = set([a, st])
    stack = [st]
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf not in used:
                stack.append(vf)
                used.add(vf)
    if len(used) == N:
        return 'Yes'
    return 'No'
Edge = [[] for _ in range(N)]
Dim = [0]*N

for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a] += 1
    Dim[b] += 1

print(check(Edge, Dim))

Submission status: Wrong Answer

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

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

deg = [len(A) for A in adj]
f = []
for i in range(1, N+1):
    if deg[i] % 2 == 1:
        print('No')
        exit()
    elif deg[i] >= 6:
        print('Yes')
        exit()
    elif deg[i] == 4:
        f.append(i)

if len(f) >= 3:
    print('Yes')
    exit()

if len(f) <= 1:
    print('No')
    exit()

t1, t2 = f[0], f[1]
seen = [0] * (N+1)
for v0 in range(1, N+1):
    if seen[v0] == 0 and v0 != t1 and v0 != t2:
        st = [v0]
        seen[v0] = 1
        dest = []
        while st:
            v = st.pop()
            for u in adj[v]:
                if u == t1:
                    dest.append(t1)
                    continue
                if u == t2:
                    dest.append(t2)
                    continue
                if seen[u] == 0:
                    seen[u] = 1
                    st.append(u)
        if dest[0] == dest[1]:
            print('Yes')
            exit()

print('No')

Submission status: Wrong Answer

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

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

deg = [len(A) for A in adj]
f = []
for i in range(1, N+1):
    if deg[i] % 2 == 1:
        print('No')
        exit()
    elif deg[i] >= 6:
        print('Yes')
        exit()
    elif deg[i] == 4:
        f.append(i)

if len(f) >= 3:
    print('Yes')
    exit()

if len(f) <= 1:
    print('No')
    exit()

v1, v2 = f[0], f[1]
u1 = adj[v1][0]
seen = [0] * (N+1)
seen[v1] = 1
c = 0
while True:
    seen[u1] = 1
    u1_new = adj[u1][0]
    if seen[u1_new] == 1:
        u1_new = adj[u1][1]
    if u1_new == v1:
        u2 = u1
        break
    if u1_new == v2:
        c += 1
    u1 = u1_new

u34 = []
for u in adj[v1]:
    if seen[u] == 0:
        u34.append(u)
u3, u4 = u34
while True:
    seen[u3] = 1
    u3_new = adj[u3][0]
    if seen[u3_new] == 1:
        u3_new = adj[u3][1]
    if u3_new == v1:
        break
    if u3_new == v2:
        c += 1
    u3 = u3_new

if c == 2:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

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

N,M=map(int,input().split())
EDGE=[tuple(map(int,input().split())) for i in range(M)]

E=[[] for i in range(N+1)]
J=[0]*(N+1)

for x,y in EDGE:
    J[x]+=1
    J[y]+=1

    E[x].append(y)
    E[y].append(x)

from collections import deque
Q=deque()
Q.append(1)

USE=[0]*(N+1)

while Q:
    x=Q.pop()

    for to in E[x]:
        if USE[to]==0:
            Q.append(to)
            USE[to]=1

if min(USE[1:])==0:
    print("No")
    sys.exit()

for i in range(N+1):
    if J[i]%2==1:
        print("No")
        sys.exit()

if max(J)>=6:
    print("Yes")
    sys.exit()

if sum(J)<=2*N+2:
    print("No")
    sys.exit()

FOUR=[]
for i in range(N+1):
    if J[i]==4:
        FOUR.append(i)

Q=deque()
Q.append(FOUR[0])
USE=[0]*(N+1)

count=0

while Q:
    x=Q.pop()

    for to in E[x]:
        if to==FOUR[1]:
            count+=1
            continue
            
        if USE[to]==0:
            Q.append(to)
            USE[to]=1

if count==2:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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

N,M = map(int,input().split())
AB = [tuple(int(x) for x in input().split()) for _ in range(M)]

graph = [set() for _ in range(N+1)]
for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)

deg = [len(x) for x in graph]

def solve():
    cycle = 0
    # まず次数2の頂点を全部縮約する
    # 自己ループは取り去っちゃってよい
    V2 = set(i for i,x in enumerate(deg) if x == 2)
    V = set(range(1,N+1))
    while V2:
        v = V2.pop()
        a = graph[v].pop()
        b = graph[v].pop()
        deg[v] = 0
        graph[a].remove(v)
        graph[b].remove(v)
        if b in graph[a]:
            cycle += 1
            graph[a].remove(b)
            graph[b].remove(a)
            deg[a] -= 2
            deg[b] -= 2
            if deg[a] == 2:
                V2.add(a)
            if deg[b] == 2:
                V2.add(b)
            if deg[a] == 0:
                V2.remove(a)
                V.remove(a)
            if deg[b] == 0:
                V2.remove(b)
                V.remove(b)
        else:
            graph[a].add(b)
            graph[b].add(a)
        V.remove(v)
    n = len(V)
    return cycle >= 3 or n >= 3

answer = 'Yes' if solve() else 'No'
print(answer)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a, b = zip(*(map(int, input().split()) for _ in range(M)))


G = [set() for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x].add(y)
    G[y].add(x)


# 次数4の頂点間のパスの数が4でないならばTrueを返す
def f():
    x, y = (i for i in range(1, N + 1) if len(G[i]) == 4)
    q = []
    dp = [0 for _ in range(N + 1)]
    q.append(x)
    dp[x] = 1
    while q:
        i = q.pop()
        for j in G[i]:
            if j == y or dp[j] == 0:
                dp[j] += 1
                q.append(j)
    return dp[y] != 4


# 以下のいずれかを満たすならば、かつ、そのときに限りYes
# - 次数4の頂点間を結ぶ異なる4つのパスが存在しない場合
# - 各頂点の次数は2または4であり、次数4の頂点は3個存在する場合
# - 各頂点の次数は偶数であり、次数が6以上の頂点が存在する場合
ans = (
    'Yes' if (
        all(len(G[i]) % 2 == 0 for i in range(1, N + 1)) and
        (
            any(len(G[i]) >= 6 for i in range(1, N + 1)) or
            sum(len(G[i]) == 4 for i in range(1, N + 1)) >= 3 or
            sum(len(G[i]) == 4 for i in range(1, N + 1)) == 2 and f()
        )
    ) else
    'No'
)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
import copy
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)



N, M = list(map(int, input().split()))


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

closs = 0

for i in range(N):
   if len(graph[i]) % 2 != 0:
       print("No")
       exit()
   if len(graph[i]) >= 4:
       closs += len(graph[i]) / 2 - 1

if closs < 2:
    print("No")
    exit()

print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
import copy
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)



N, M = list(map(int, input().split()))

if N < 6 or M < 9:
    print("No")
    exit()

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

closs = 0

for i in range(N):
   if len(graph[i]) % 2 != 0:
       print("No")
       exit()
   if len(graph[i]) >= 4:
       closs += len(graph[i]) / 2 - 1

if closs < 2:
    print("No")
    exit()

print("Yes")

Submission status: Wrong Answer

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

for i in range(m):
    a,b=map(int,input().split())
    C[a-1].append(b)
    C[b-1].append(a)

#print(C)

ans="No"
cnt=0

for i in range(n):
    lenC=len(C[i])
    if lenC%2==1:
        break
    elif lenC !=2:
        cnt+=lenC
else:
    if cnt>=6:
        ans="Yes"
        
        
print(ans)

Submission status: Wrong Answer

Solution code:
# AtCoder Grand Contest 032

'''
オイラーグラフ：すべての頂点の次数が偶数
準オイラーグラフ：次数が奇数であるものが丁度2つ
オイラーグラフであることが前提
'''
import sys

N,M = map(int,sys.stdin.readline().rstrip().split())
array = []
for i in range(M):
    array.append(list(map(int,sys.stdin.readline().rstrip().split())))

edge_num = [0 for i in range(N)]
for i in array:
    edge_num[i[0]-1] += 1
    edge_num[i[1]-1] += 1

for i in edge_num:   #　オイラーグラフである条件
    if i % 2 == 1:
        print('No')
if 6 in edge_num:
    print('Yes')
elif edge_num.count(4) == 3:
    print('Yes')
elif edge_num.count(4) == 2:
    ind = [i+1 for i, x in enumerate(edge_num) if x == 4]
    check = 0
    for i in array:
        if i[0] == ind[0] and i[1] == ind[1]:
            check += 1
        if i[0] == ind[1] and i[1] == ind[0]:
            check += 1
        if check > 2:
            print('No')
            exit()
    if check == 2:
        print('Yes')
    else:
        print('No')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys

N,M = map(int,sys.stdin.readline().rstrip().split())
array = []
for i in range(M):
    array.append(list(map(int,sys.stdin.readline().rstrip().split())))

edge_num = [0 for i in range(N)]
for i in array:
    edge_num[i[0]-1] += 1
    edge_num[i[1]-1] += 1

for i in edge_num:   #　オイラーグラフである条件
    if i % 2 == 1:
        print('No')

if 6 in edge_num:
    print('Yes')
elif edge_num.count(4) == 3:
    print('Yes')
elif edge_num.count(4) == 2:
    ind = [i for i, x in enumerate(edge_num) if x == 4]
    check = 0
    for i in array:
        if i[0] == ind[0] and i[1] == ind[1]:
            check += 1
        if i[0] == ind[1] and i[1] == ind[0]:
            check += 1
        if check > 2:
            print('No')
            exit()
    if check == 2:
        print('Yes')
    else:
        print('No')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys

N,M = map(int,sys.stdin.readline().rstrip().split())
array = []
for i in range(M):
    array.append(list(map(int,sys.stdin.readline().rstrip().split())))

edge_num = [0 for i in range(N)]
for i in array:
    edge_num[i[0]-1] += 1
    edge_num[i[1]-1] += 1

for i in edge_num:   #　オイラーグラフである条件
    if i % 2 == 1:
        print('NO')

if 6 in edge_num:
    print('YES')
elif edge_num.count(4) == 3:
    print('YES')
elif edge_num.count(4) == 2:
    ind = [i for i, x in enumerate(edge_num) if x == 4]
    check = 0
    for i in array:
        if i[0] == ind[0] and i[1] == ind[1]:
            check += 1
        if i[0] == ind[1] and i[1] == ind[0]:
            check += 1
        if check > 2:
            print('NO')
            exit()
    if check == 2:
        print('YES')
    else:
        print('NO')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
import sys
 
a = list(map(int,input().split()))
counter= [0]*a[0]
check=[0]*a[0]
for i in range(a[1]):
    x,y=map(int,input().split())
    counter[x-1] += 1
    counter[y-1] += 1
    check[x-1] += 1
    check[y-1] += 1
    check[x-1] %= 2
    check[y-1] %= 2
 
if (sum(check) != 0 or sum(counter) < (a[0]*2+4)):
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
a = list(map(int,input().split()))

list = []
for i in range(a[1]):
    x,y=input().split()
    list.append((int(x), int(y)))

z=[]
for s in list:
    z.extend(s)
f=0
s=0
for j in range(1,a[0]+1):
    if z.count(j) == 4:
        f += 1
    if z.count(j) > 5:
        s += 2
    if z.count(j) % 2 != 0:
        f=0
        s=0
        break

if f + s >= 2 and a[1] >=9:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
# input
n, m = (int(i) for i in input().split())
edges = set()
for i in range(m):
    edges.add(tuple(int(i) for i in input().split()))

walks = set()


def contain(path: list, vtx: tuple):
    ''' whether path contain vtx
    '''
    for edge in path:
        if vtx in edge:
            return True
    return False


def extract_closed_path(edges: list):
    path = []
    vtx_history = []
    # start
    cur_vtx = edges[0][0]

    while True:
        vtx_history.append(cur_vtx)
        con_edge, cur_vtx = get_connected_edge_vtx(edges, cur_vtx)
        if con_edge is None:
            # no connected edge has been found
            break
        path.append(con_edge)
        edges.remove(con_edge)
        if cur_vtx in vtx_history:
            # closed path found, but it may be imperfect (like 9 or 6, not 0)
            return path
    # in this code, no closed path has been found
    return None


def find_junction(closed_path: list):
    ''' find junction or loop start point from closed path
    '''
    cand = closed_path[-1]
    return cand[0] if cand[0] not in closed_path[-2] else cand[1]


def extract_loop(closed_path: list):
    junction = find_junction(closed_path)
    circuit = set()
    count = 0
    for edge in reversed(closed_path):
        if junction in edge:
            count += 1
            if count > 2:
                break
        circuit.add(edge)
    return circuit


def get_connected_edge_vtx(edges, vertex):
    for edge in edges:
        if vertex in edge:
            counter = edge[0] if edge[0] != vertex else edge[1]
            return edge, counter
    return None, None

# circuit = []

def extract_circuit(edges):

    unexplors = list(edges - walks)
    closed_path = extract_closed_path(unexplors)
    if closed_path is None:
        return None, None
    circuit = extract_loop(closed_path)
    return circuit, edges - circuit

circuits = []

for i in range(3):
    try:
        circuit, edges = extract_circuit(edges)
        circuits.append(circuit)
    except:
        break

print('Yes' if len(circuits) == 3 else 'No')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

E = {a: set() for a in range(1, N + 1)}
for i in range(M):
    a, b = map(int, input().split())
    E[a].add(b)
    E[b].add(a)

def degree(a): return len(E[a])
def nodes():   return range(1, N + 1)

def removeOneCycle():
    """適当なcycleを削除"""
    lasso = {} # 投げ縄
    a = [a for a in nodes() if degree(a) > 0][0] # 適当な開始節点
    p = None
    while a not in lasso:
        lasso[a] = [b for b in E[a] if b != p][0] # 引き返し以外
        p, a = a, lasso[a]
    start = a
    b = None
    while b != start:
        b = lasso[a]
        E[a].remove(b)
        E[b].remove(a)
        a = b

yes = all(degree(a) % 2 == 0 for a in nodes())
if yes:
    removeOneCycle()
    yes = any(degree(a) >= 4 for a in nodes())

print('Yes' if yes else 'No')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

E = {a: set() for a in range(1, N + 1)}
for i in range(M):
    a, b = map(int, input().split())
    E[a].add(b)
    E[b].add(a)

def removeCircuit(start):
    """startから始まる適当なcircuitを削除"""
    a = start
    b = None
    while b != start:
        b = E[a].pop()
        E[b].remove(a)
        a = b

yes = all(len(E[a]) % 2 == 0 for a in range(1, N + 1))
if yes:
    removeCircuit(1)
    yes = any(len(E[a]) >= 4 for a in range(1, N + 1))

print('Yes' if yes else 'No')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
E = []
for i in range(M):
    a, b = map(int, input().split())
    E.append((a, b))

def degrees(E):
    """D[i-1] == iの次数"""
    D = [0] * N
    for a, b in E:
        D[a - 1] += 1
        D[b - 1] += 1
    return D

D = degrees(E)
yes = all(D[a] % 2 == 0 for a in range(N)) and \
     (any(D[a] >= 6 for a in range(N)) or \
      sum(1 for a in range(N) if D[a] >= 4) >= 2)
print('Yes' if yes else 'No')

Submission status: Wrong Answer

Solution code:
class Queue:
    def __init__(self):
        self.__count = 0
        self.__data = []

    def count(self) -> int:
        return self.__count

    def empty(self) -> bool:
        return self.__count == 0

    def front(self):
        if self.empty():
            raise Exception('empty')
        return self.__data[0]

    def dequeue(self):
        if self.empty():
            raise Exception('empty')
        res, self.__data = self.__data[0], self.__data[1:]
        self.__count -= 1
        return res

    def enqueue(self, v):
        self.__data.append(v)
        self.__count += 1


class Edge:
    def __init__(self, v: int, cap: int, rev: int):
        """
        :param v: to
        :param cap: capacity
        :param rev: revesed to
        """
        self.v = v
        self.cap = cap
        self.rev = rev

        self.flow = 0


class Graph:
    def __init__(self, num_v: int):
        """
        :param num_v: number of vertex
        """
        self.num_v = num_v
        self.level = [0] * num_v
        self.graph = [[] for _ in range(num_v)]

    def add_edge(self, u: int, v: int, cap: int):
        """add edge
        :param u: from
        :param v: to
        :param cap: capacity
        """
        forward = Edge(v, cap, len(self.graph[v]))
        back = Edge(u, 0, len(self.graph[u]))

        self.graph[u].append(forward)
        self.graph[v].append(back)

    def __bfs(self, s: int, t: int) -> bool:
        """Finds if more flow can be sent from s to t.
        Also assigns level to nodes.
        :param s: source
        :param t: sink
        :return: `True` if finds more flow can be sent from s to t.
        """
        self.level = [-1] * self.num_v
        self.level[s] = 0

        q = Queue()
        q.enqueue(s)
        while not q.empty():
            u = q.dequeue()

            for e in self.graph[u]:
                # not yet visited, and flow can be sent more
                if self.level[e.v] < 0 and e.flow < e.cap:
                    # level of v is level of its parent + 1
                    self.level[e.v] = self.level[u] + 1

                    q.enqueue(e.v)

        return self.level[t] >= 0

    def __send_flow(self,
                    u: int, flow: int, t: int, start: list = None) -> int:
        """send `flow` from `u` to `t`.
        :param u: from
        :param flow: flow
        :param t: to
        :param start: explored vertex
        :return: value of flow can be sent from u to t.
        """
        if u == t:
            return flow

        if start is None:
            start = [0] * (self.num_v + 1)

        while start[u] < len(self.graph[u]):
            e = self.graph[u][start[u]]

            if self.level[e.v] != self.level[u] + 1:
                # skip if level of e.v is not next to
                # u's one.
                start[u] += 1
                continue
            if not (e.flow < e.cap):
                # skip if flow cannot be sent more to
                # v.
                start[u] += 1
                continue

            cur_f = min(flow, e.cap - e.flow)
            tmp_f = self.__send_flow(e.v, cur_f, t, start)

            if tmp_f > 0:
                # add flow to current edge
                e.flow += tmp_f
                # subtract flow from reverse edge of current one.
                self.graph[e.v][e.rev].flow -= tmp_f

                return tmp_f

            start[u] += 1

        return 0

    def maximum_flow(self, s: int, t: int) -> int:
        """maximum flow from s to t.
        :param s: from
        :param t: to
        :return: maximum flow
        """
        if s == t:
            return 0

        max_flow = 0
        while self.__bfs(s, t):
            while True:
                flow = self.__send_flow(s, float('inf'), t)
                if flow == 0:
                    break
                max_flow += flow
        return max_flow


def three_circuit(N: int, M: int, edges: list) -> bool:
    dims = [0] * N  # dims[n] = 頂点 n の次数
    g = Graph(N)

    for u, v in edges:
        dims[u-1] += 1
        dims[v-1] += 1

        g.add_edge(u-1, v-1, 1)
        g.add_edge(u-1, v-1, 1)

    if not all(d % 2 == 0 for d in dims):
        # オイラー閉路でない
        return False

    if max(dims) >= 6:
        # 次元数が 6 以上の頂点があるならそいつを利用して
        # 3 つのサーキットが作れる。
        return True

    # 次元数 4 の頂点集合
    vertexes = [v for v in range(N) if dims[v] == 4]

    if len(vertexes) >= 3:
        # 次元数 4 の頂点が 3 つ以上存在するなら OK
        return True

    if len(vertexes) == 2:
        # 次元数 4 の頂点が 2 つのみ存在する場合、ありうるのは、この
        # 2 頂点の間にパスが 4 つある場合と 2 つある場合。
        # 前者は図を書けばすぐわかるが高々 2 つのサーキットしか作れな
        # い。後者の場合は、この 2 頂点を含むサーキットが 1 つとそれ
        # ぞれの頂点しか含まないサーキットが 1 つずつ、計 3 つ作れる。

        # 最大フロー・最小カットの定理より、最小カットが求まり、s-t
        # 間のパスが求められる。
        s, t = vertexes
        path = g.maximum_flow(s, t)
        return path == 2

    # 残りは 次数 4 の点が 1 つ、あるいはすべての頂点の次数が 2 となる。
    # 前者の場合、高々 2 つのサーキット、後者の場合は高々 1 つのサーキッ
    # トしか作れないのは自明。
    return False


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(int(s) for s in input().split()) for _ in range(M)]

    yes = three_circuit(N, M, edges)
    print('Yes' if yes else 'No')

Submission status: Wrong Answer

Solution code:
# AGC032 Problem-C

n, m = map(int,input().split())

check = [0 for i in range(0,n)]
#table = [[0 for i in range (0,n)] for j in range (0,n)]
for i in range(0,m) :
    a, b = map(int,input().split())
    check[a-1] += 1
    check[b-1] += 1
#print (check)

node4 = 0
node6 = 0
node_odd = 0
for i in range(0,n):
    if check[i] % 2 == 0:
        if check[i]==4 :
            node4 += 1
        if check[i]>=6 :
            node6 +=1
    else:
        node_odd += 1

if (node_odd == 0) and ((node4 >= 2) or (node6 >=1)) :
    print ("Yes")
else:
    print ("No")

#def solve() :

Submission status: Wrong Answer

Solution code:
# AGC032 Problem-C

n, m = map(int,input().split())

table = [[0 for i in range (0,n)] for j in range (0,n)]
for i in range(0,m) :
    a, b = map(int,input().split())
    table[a-1][b-1] = 1
    table[b-1][a-1] = 1
#print (table)

check = [0 for i in range(0,n)]
for i in range(0,n):
    for j in range(0,n):
        check[i] += table[i][j]
#print (check)

node4 = 0
node6 = 0
node_odd = 0
for i in range(0,n):
    if check[i] % 2 == 0:
        if check[i]==4 :
            node4 += 1
        if check[i]>=6 :
            node6 +=1
    else:
        node_odd += 1

if (node_odd == 0) and ((node4 >= 2) or (node6 >=1)) :
    print ("yes")
else:
    print ("no")

Submission status: Wrong Answer

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

def main():
    n,m=map(int,input().split())
    Edges=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        a-=1; b-=1
        Edges[a].append(b)
        Edges[b].append(a)
        F=[]
        l=0
    for i,E in enumerate(Edges):
        e=len(E)
        if e%2:
            return 'No'
        if e==4:
            F.append(i)
        if e>=6:
            l+=1
    if l:
        return 'Yes'
    if len(F)<2:
        return 'No'
    if len(F)>2:
        return 'Yes'
    s,t=F[0],F[1]
    for v in Edges[s]:
        Visited=[False]*n
        Visited[s]=True
        while v!=t:
            Visited[v]=True
            for to in Edges[v]:
                if not Visited[to]:
                    v==to
                    break
            if Visited[v]:
                break
        if v!=t:
            return 'Yes'
    return 'No'

print(main())