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

Solution code:
import sys
sys.setrecursionlimit(100000)

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

count = [0] * (N)
E = [[] for _ in range(N)]

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

count_sum = 0
count4 = 0
count6 = 0
node = 0

check = [False] * N

for i, temp in enumerate(count):
    if temp % 2 == 1:
        print("No")
        exit()
    else:
        if temp >= 4:
            count4 += 1
            check[i] = True
            node = i
        if temp >= 6:
            count6 += 1
        count_sum += temp

def dfs(v, first, depth):
    global E, check

    ret = 0
    for next_v in E[v]:
        if depth >= 2 and next_v == first:
            return 1
        elif not check[next_v]:
            check[next_v] = True
            ret += dfs(next_v, first, depth + 1)

    return ret

if count4 >= 3 or count6 >= 1:
    print("Yes")
elif count4 == 2:
    ret = dfs(node, node, 0)
    if ret > 0:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def solve():
    N, M = map(int, input().split())
    F = [list() for _ in range(N+1)]
    D = [int() for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        D[a] += 1
        D[b] += 1
        F[a].append(b)
        F[b].append(a)

    E = [0 for _ in range(7)]
    X = list()
    for a,d in enumerate(D[1:], start=1):
        if d%2==0:
            if d >= 6:
                E[6] += 1
            elif d == 4:
                E[4] += 1
                X.append(a)
            else:
                E[d] += 1
        else:
            return 'No'
            E[1] += 1

    if E[6]>0 or E[4]>2:
        return 'Yes'

    elif E[4]<2:
        return 'No'

    else:
        x, y = X
        q = set((y,))
        R = set((x,))
        while q:
            z = q.pop()
            R.add(z)
            q |= set(F[z])-R
        if set(F[x])&R == set(F[x]):
            return 'No'
        else:
            return 'Yes'

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import sys


def solve(n, m, links):
    v4 = set()
    v6 = 0
    for v, link in enumerate(links):
        l = len(link)
        if l % 2 == 1:
            return False
        if l == 4:
            v4.add(v)
        elif l >= 6:
            v6 += 1
    if v6 > 0:
        return True
    if len(v4) > 2:
        return True
    if len(v4) < 2:
        return False
    s = v4.pop()
    t = v4.pop()
    for c in links[s]:
        visited = {s, t}
        q = [c]
        while q:
            v = q.pop()
            if v in visited:
                continue
            visited.add(v)
            for u in links[v]:
                if v != c and u == s:
                    return True
                if u not in visited:
                    q.append(u)
    return False


n, m = map(int, input().split())
links = [set() for _ in [0] * n]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('Yes' if solve(n, m, links) else 'No')

Submission status: Accepted

Solution code:
from collections import deque
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, readline().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)
def check(s, t):
    u = [0]*N
    u[s] = u[t] = 1
    for v in G[s]:
        if v == t:
            continue
        u[v] = 1
        que = deque([v])
        ok = 0
        while que:
            x = que.popleft()
            for y in G[x]:
                if y == s and x != v:
                    return 1
                if u[y]:
                    continue
                u[y] = 1
                que.append(y)
    return 0
C = [0]*4
ok = 1
for i in range(N):
    if len(G[i]) % 2 == 1:
        ok = 0
    C[min(3, len(G[i])//2)] += 1
if C[1] == N or (C[1] == N-1 and C[2] == 1):
    ok = 0
elif C[1] == N-2 and C[2] == 2:
    VV = []
    for i in range(N):
        if len(G[i]) == 4:
            VV.append(i)
    if not check(*VV):
        ok = 0
print("Yes" if ok else "No")

Submission status: Runtime Error

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")
elif jdg == 2:
  print(2/0)
else:
  print("No")

Submission status: Runtime Error

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()
print(1/0)
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: Runtime Error

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():
    assert 0
    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: Runtime Error

Solution code:
n, m = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]

def find_single_self_loop(start, prev, n):
    if prev != -1 and len(edge[n]) != 2:
        if n == start:
            return True
        else:
            return False
    for item in edge[n]:
        if item == prev:
            continue
        ret = find_single_self_loop(start, n, item)
        if ret:
            return True
    return False

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

order = [0] * (10**5 + 10)
# Must be Euler graph
for i, line in enumerate(edge):
    o = len(line)
    order[o] += 1
    if o % 2 != 0:
        print("No")
        exit()
    if o >= 4:
        index = i

# Existance of over order-6 node means graph includes over 3 circuits
if max(order[6:]) > 0:
    print("Yes")
    exit()

print(order[:10])
# only 1 order-4 up to 2 circuit
if order[4] <= 1:
    print("No")
    exit()
# over 3 order-4 includes over 3 circuits 
elif order[4] >= 3:
    print("Yes")
    exit()
# 2 order-4
else:
    ret = find_single_self_loop(index, -1, index)
    if ret:
        print("Yes")
    else:
        print("No")

Submission status: Runtime Error

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

Solution code:
import sys
import pandas as pd

### 方針
### 全ての点が遇点であり、接続する辺の数が４の点が２つ以上あるいは、接続する辺の数が６つ以上の点が１つ以上で成立

# 標準入力を受け取る
##  1行目だけ単体で取得。残りの行数と購入本数把握のため
##  a[0]：頂点数、a[1]：辺数
a = list(map(int,input().split()))

##  残りの行を取得する
list = []
for i in range(a[1]):
    x,y=input().split()
    # 頂点to頂点
    list.append((int(x), int(y)))

z=[]
for s in list:
    z.extend(s)
### 遇点の数を数える
#### 要素の出現回数をカウントする
f=0 #4の出現回数
s=0 #6以上の出現回数
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: Runtime Error

Solution code:
import sys
import pandas as pd

### 方針
### 全ての点が遇点であり、接続する辺の数が４の点が２つ以上あるいは、接続する辺の数が６つ以上の点が１つ以上で成立

# 標準入力を受け取る
##  1行目だけ単体で取得。残りの行数と購入本数把握のため
##  a[0]：頂点数、a[1]：辺数
a = list(map(int,input().split()))

##  残りの行を取得する
list = []
for i in range(a[1]):
    x,y=input().split()
    # 頂点to頂点
    list.append((int(x), int(y)))

z=[]
for s in list:
    z.extend(s)
### 遇点の数を数える
#### 要素の出現回数をカウントする
f=0 #4の出現回数
s=0 #6以上の出現回数
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: Runtime Error

Solution code:
def has_circuit(g: list, s: int, ng: int) -> bool:
    stack = []
    stack.append((s, -1))  # (現在の頂点, 親)

    visited = [False] * len(g)
    visited[s] = True

    while len(stack) > 0:
        u, p = stack.pop()

        if u == s and p >= 0:
            return True

        visited[u] = True

        for v in g[u]:
            if visited[v]:
                continue
            if v == ng:
                continue
            if v == p:
                continue
            stack.append((v, u))
    return False


def three_circuit(N: int, M: int, edges: list) -> bool:
    g = [[] for _ in range(N)]

    for u, v in edges:
        g[u-1].append((v-1, 1))
        g[v-1].append((u-1, 1))

    dims = [len(p) for p in g]

    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 つ作れる。

        # 次数 4 の頂点からスタートしてほかの次数 4 の頂点に出会わずに
        # 帰ってこれるパスが存在すれば次数 4 の頂点間にはパスがちょうど
        # 2 つとなる。
        return has_circuit(g, vertexes[0], vertexes[1])

    # 残りは 次数 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: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
c=[0]*n
for j in range(m):
  a,b=[int(i) for i in input().split()]
  c[a]+=1
  c[b]+=1
d=True
e=0
for i in c:
  if i%2!=0:
    d=False
  e+=i-2
if d and e>3:
  print("Yes")
else:
  print("No")

Submission status: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
c=[0]*n
for j in m:
  a,b=[int(i) for i in input().split()]
  c[a]+=1
  c[b]+=1
d=True
e=0
for i in c:
  if i%2!=0:
    d=False
  e+=i-2
if d and e>3:
  print("Yes")
else:
  print("No")

Submission status: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
c=[0]*n
for j in m:
  a,b=[int(i) for i in input().split()]
  c[a]+=1
  c[b]+=1
d=True
e=0
for i in c:
  if i%2!=0:
    d=False
  e+=i-2
if d and e>3:
  print("Yes")
else:
  print("No)

Submission status: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
c=[0]*n
for j in m:
  a,b=[int(i) for i in input().split()]
  c[a]+=1
  c[b]+=1
d=True
e=0
for i in c:
  if i%2!=0:
    d=False
    e+=i-2
if d and e>3:
  print("Yes")
else:
  print("No)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
c = 0
d = 0
for _ in range(100):
    a, b = map(int, input().split())
print("No")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 解説PDFを見て実装
#
# サーキットとは、辺を2回通らない経路のこと。要は一筆書きでできる経路。
#
# もし、あるグラフが、「全ての辺をちょうど 
# 1回ずつ使って3つのサーキットを作ることができる」条件を満たすとする。
#
# すると、グラフ全体は必ずオイラー路（すべての辺を使う閉路）でないといけない
# ことがわかる。
#
# オイラー路ができる必要十分条件は、全ての頂点の次数が偶数である
# ことを思い出す。これを満たしていなければ問題外。
# ここまでは気付きたかった。
#
# このあとはひたすら場合分け。解説PDFそのまま。
# 次数4の頂点が2個ある場合のコーナーケースに注意。

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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

edges = defaultdict(list)
edge_num = Counter()
for m in range(M):
    a, b = map(int, input().split())
    edge_num[a] += 1
    edge_num[b] += 1
    edges[a].append(b)
    edges[b].append(a)

def solve():
    values = edge_num.values()

    for v, num in edge_num.items():
        if num % 2 == 1:
            return False

    four = []
    for v, num in edge_num.items():
        if num >= 6:
            return True
        if num >= 4:
            four.append(v)

    if len(four) >= 3:
        return True
    if len(four) <= 1:
        return False

    # 一方の頂点からもう一方の頂点へのパスの数を数える
    v0 = four[0]
    v1 = four[1]
    path_num = 0

    def dfs(v, from_v):
        for child in edges[v]:
            if child == from_v:
                continue
            else:
                if child == v1:
                    return 1
                elif child == v0:
                    return 0
                else:
                    return dfs(child, v)

    for child in edges[v0]:
        path_num += dfs(child, v0)

    if path_num == 4:
        return False
    elif path_num == 2:
        return True

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 解説PDFを見て実装
#
# サーキットとは、辺を2回通らない経路のこと。要は一筆書きでできる経路。
#
# もし、あるグラフが、「全ての辺をちょうど 
# 1回ずつ使って3つのサーキットを作ることができる」条件を満たすとする。
#
# すると、グラフ全体は必ずオイラー路（すべての辺を使う閉路）でないといけない
# ことがわかる。
#
# オイラー路ができる必要十分条件は、全ての頂点の次数が偶数である
# ことを思い出す。これを満たしていなければ問題外。
# ここまでは気付きたかった。
#
# このあとはひたすら場合分け。解説PDFそのまま。
# 次数4の頂点が2個ある場合のコーナーケースに注意。

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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

edges = defaultdict(list)
edge_num = Counter()
for m in range(M):
    a, b = map(int, input().split())
    edge_num[a] += 1
    edge_num[b] += 1
    edges[a].append(b)
    edges[b].append(a)

def solve():
    values = edge_num.values()

    four = []
    for v, num in edge_num.items():
        if num % 2 == 1:
            return False
        if num >= 6:
            return True
        if num >= 4:
            four.append(v)

    if len(four) >= 3:
        return True
    if len(four) <= 1:
        return False

    # 一方の頂点からもう一方の頂点へのパスの数を数える
    v0 = four[0]
    v1 = four[1]
    path_num = 0

    def dfs(v, from_v):
        for child in edges[v]:
            if child == from_v:
                continue
            else:
                if child == v1:
                    return 1
                elif child == v0:
                    return 0
                else:
                    return dfs(child, v)

    for child in edges[v0]:
        path_num += dfs(child, v0)

    if path_num == 4:
        return False
    elif path_num == 2:
        return True

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

Submission status: Runtime Error

Solution code:

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

deg = [0 for i in range(N)]
for i in a:
    for j in i:
        try:
            deg[j-1] +=1
        except IndexError:
            continue

if max(deg) >= 6:
    print("Yes")
else:
    num = deg.count(4)
    if num == 0 or num == 1:
        print("No")
    elif num >= 3:
        print("Yes")
    else:
        prinnt("No")

Submission status: Runtime Error

Solution code:
import sys

def ta(x, y, p):
    xc = 0
    yc = 0

    for i in p[x]:
        c = i
        while True:
            if c == x:
                xc += 1
                break
            elif c == y:
                yc += 1
                break
            cs = p[c]
            for j in cs:
                if j != bc:
                    bc = c
                    c = j
                    break
    if xc == yc:
        return True
    else:
        return False


d = {}
p = {}
n, m = input().strip().split(" ")
for i in range(int(n)):
    i += 1
    d[i] = 0
    p[i] = list()

for line in sys.stdin:
    x, y = line.strip().split(" ")
    x, y = int(x), int(y)
    d[x] += 1
    d[y] += 1
    p[x].append(y)
    p[y].append(x)

r = None
fc = 0
fcs = []
for x in d.values():
    if x % 2 != 0:
        r = False
        break
    if x >= 6:
        r = True
    if x >= 4:
        fc += 1
        fcs.append(x)

if r == None:
    if fc >= 3:
        r = True
    elif fc == 2:
        x, y = fcs
        r = ta(x, y, p)
    else:
        r = False
if r:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
# class Graph:
#     def __init__(self, V: int):
#         self.__V = V
#         self.__g = [[] for _ in range(V)]
#         self.__used = [False] * V

#     def add_edge(self, u: int, v: int, cap: int):
#         self.__g[u].append((v, cap, len(self.__g[v])))
#         self.__g[v].append((u, 0, len(self.__g[u])-1))

#     def ford_fulkerson(self, s: int, t: int)->int:
#         flow = 0
#         while True:
#             self.__used = [False] * self.__V
#             f = self.__dfs(s, t, float('inf'))
#             if f == 0:
#                 break
#             flow += f
#         return flow

#     def __dfs(self, v: int, t: int, f: int)->int:
#         if v == t:
#             return f
#         self.__used[v] = True

#         for i, (to, cap, rev) in enumerate(self.__g[v]):
#             if (not self.__used[to]) and cap > 0:
#                 d = self.__dfs(to, t, min(f, cap))

#                 if d > 0:
#                     self.__g[v][i] = (to, cap-d, rev)

#                     _to, _cap, _rev = self.__g[to][rev]
#                     self.__g[to][rev] = (_to, _cap+d, _rev)

#                     return d
#         return 0


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_circuits(N: int, M: int, edges: list)->bool:
    d = [0] * N

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

    if any(v & 1 == 1 for v in d):
        # euler 閉路でないなら NG
        return False
    if any(v >= 6 for v in d):
        # 次数が 6 以上のものがあれば OK
        return True

    c4 = d.count(4)
    if c4 > 2:
        # 次数が 4 のものが 3 つ以上存在すれば OK
        return True
    if c4 < 2:
        # 次数が 4 のものが 1 つ以下なら NG
        return False

    # 次数が 4 のものが 2 つならその二つの頂点間にパスが二つ
    # の時のみ OK
    graph = Graph(N+1)
    # print('-' * 30)
    for u, v in edges:
        graph.add_edge(u-1, v-1, 1)
        graph.add_edge(v-1, u-1, 1)

    u = d.index(4)
    v = d.index(4, u+1)
    # print(d)

    return graph.maximum_flow(u, v) == 2
    # return False


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(M)]
    yes = three_circuits(N, M, edges)
    print('Yes' if yes else 'No')

Submission status: Runtime Error

Solution code:
# class Graph:
#     def __init__(self, V: int):
#         self.__V = V
#         self.__g = [[] for _ in range(V)]
#         self.__used = [False] * V

#     def add_edge(self, u: int, v: int, cap: int):
#         self.__g[u].append((v, cap, len(self.__g[v])))
#         self.__g[v].append((u, 0, len(self.__g[u])-1))

#     def ford_fulkerson(self, s: int, t: int)->int:
#         flow = 0
#         while True:
#             self.__used = [False] * self.__V
#             f = self.__dfs(s, t, float('inf'))
#             if f == 0:
#                 break
#             flow += f
#         return flow

#     def __dfs(self, v: int, t: int, f: int)->int:
#         if v == t:
#             return f
#         self.__used[v] = True

#         for i, (to, cap, rev) in enumerate(self.__g[v]):
#             if (not self.__used[to]) and cap > 0:
#                 d = self.__dfs(to, t, min(f, cap))

#                 if d > 0:
#                     self.__g[v][i] = (to, cap-d, rev)

#                     _to, _cap, _rev = self.__g[to][rev]
#                     self.__g[to][rev] = (_to, _cap+d, _rev)

#                     return d
#         return 0


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_circuits(N: int, M: int, edges: list)->bool:
    d = [0] * N

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

    if any(v & 1 == 1 for v in d):
        # euler 閉路でないなら NG
        return False
    if any(v >= 6 for v in d):
        # 次数が 6 以上のものがあれば OK
        return True

    c4 = d.count(4)
    if c4 > 2:
        # 次数が 4 のものが 3 つ以上存在すれば OK
        return True
    if c4 < 2:
        # 次数が 4 のものが 1 つ以下なら NG
        return False

    # 次数が 4 のものが 2 つならその二つの頂点間にパスが二つ
    # の時のみ OK
    graph = Graph(N)
    # print('-' * 30)
    for u, v in edges:
        graph.add_edge(u-1, v-1, 1)
        graph.add_edge(v-1, u-1, 1)

    u = d.index(4)
    v = d.index(4, u+1)
    # print(d)

    return graph.maximum_flow(u, v) == 2
    # return False


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(M)]
    yes = three_circuits(N, M, edges)
    print('Yes' if yes else 'No')