Problem p03091 (python)

Fixed submission:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

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

sys.setrecursionlimit(1000000)

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

Buggy submission (verdict: Runtime Error):
#!/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")

Buggy submission (verdict: Runtime Error):
#!/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")