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

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

Solution code:

"""

3つの閉路が作れる条件とは？

まず作れない条件を考えてみるか
奇数個の辺が出てる頂点があったら絶対作れない

グラフは連結→4本出ている頂点が2つ以上 or 6本出てる頂点が1つ以上あるはず

二つのサーキットを合体して1つにすることは可能か？→触れていれば可能
逆にサーキット上で2回以上同じ点を通るなら2つの閉路に分割可能
全ての頂点に2本以上通っていたら一つの大きい閉路にできる？→可能そう

4本出 * 2の時だけ(本当か)曲者か？
一つでも4本出の内一つの頂点で共通の辺があれば可能？
"""
import sys
from collections import deque

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

lis =  [ [] for i in range(N) ]

for i in range(M):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

four_queue = []
nums = [0] * max(5,N+1)
for i in range(N):
    nums[len(lis[i])] += 1
    if len(lis[i]) == 4:
        four_queue.append(i)

up_six = False
four_num = nums[4]


for i in range(N+1):

    if i % 2 == 1 and nums[i] > 0:
        print ("No")
        sys.exit()

    elif i >= 6 and nums[i] > 0:
        up_six = True

if up_six or four_num > 2:
    print ("Yes")
    sys.exit()
elif four_num < 2:
    print ("No")
    sys.exit()
else:

    x = four_queue[0]
    y = four_queue[1]
    flag = False

    #print (x,y)

    for i in lis[x]:

        dis = [float("inf")] * N
        dis[x] = 0
        dis[i] = 1
        q = deque([i])
        #print ("i",i)

        while len(q) > 0:

            #print (q)

            now = q.popleft()

            for j in lis[now]:
                #print (j)
                if i != now and j == x:
                    print ("Yes")
                    sys.exit()
                elif j == y:
                    break

                elif dis[j] > dis[now] + 1:
                    dis[j] = dis[now] + 1
                    q.append(j)

print ("No")

Submission status: Accepted

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 = []
ok = 0
for i in range(1, N+1):
    if deg[i] % 2 == 1:
        print('No')
        exit()
    elif deg[i] >= 6:
        ok = 1
    elif deg[i] == 4:
        f.append(i)

if ok:
    print('Yes')
    exit()

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

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 'No'
    return 'Yes'
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: Accepted

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

if sum(J)>=2*N+6:
    print("Yes")
    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: Accepted

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():
    # そもそもeulerグラフでない場合
    if any(x&1 for x in deg):
        return False
    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: Accepted

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 and dp[j] == 0:
                q.append(j)
            dp[j] += 1
    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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
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()

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

Solution code:
import sys
from collections import deque
N,M=map(int,input().split())
L=[0]*N
table=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    table[a].append(b)
    table[b].append(a)
    L[a]+=1
    L[b]+=1
for i in range(N):
    if L[i]%2==1:
        print('No')
        sys.exit()
H=[]
for i in range(N):
    if L[i]>=6:
        print('Yes')
        sys.exit()
    if L[i]==4:
        H.append(i)
if len(H)<2:
    print('No')
    sys.exit()
if len(H)>2:
    print('Yes')
    sys.exit()
s=H[0]
t=H[1]
#print(L,table)
def f(x):
    visit=[0]*N
    S=deque()
    S.append(x)
    visit[s]=1
    visit[x]=1
    while S:
        y=S.popleft()
        if y==s:
            return True
        if y==t:
            return False
        for i in table[y]:
            if visit[i]==0:
                S.append(i)
                visit[i]=1
    return True
for x in table[s]:
    #print(f(x),x)
    if f(x):
        print('Yes')
        sys.exit()
print('No')

Submission status: Accepted

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を削除"""
    alive = [a for a in nodes() if degree(a) > 0]
    if len(alive) == 0:
        return False
    lasso = {}   # 投げ縄
    a = alive[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
    return True

yes = all(degree(a) % 2 == 0 for a in nodes()) and \
      removeOneCycle() and \
      removeOneCycle() and \
      any(degree(a) > 0 for a in nodes())

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

Submission status: Accepted

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

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

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

        for v in g[u]:
            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)
        g[v-1].append(u-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: Accepted

Solution code:
# AGC032 Problem-C
def special_case() :
    #Check 辺が4本出ているノードが2つあるケース
    #　　　2ノード間に4本の辺がある場合はNG
    #　　　2ノード間に2本の辺がある場合はOK (自分に戻るループがある)
    st = -1
    for i in range(0,n) :
        if check[i] == 4 :
            st = i
            break
    
    for i in edge[st] :
        p0 = st
        p1 = i
        while (check[p1]==2) :
            t1, t2 = edge[p1]
            if t1 == p0 :
                p0 = p1
                p1 = t2
            else: 
                p0 = p1
                p1 = t1
        if p1 == st :
            return 0
    return -1

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

check = [0 for i in range(0,n)]
edge  = [[] 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
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
#print (check)
#print(edge)

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) :
    print ("No")
else :
    if ((node4 >= 3) or (node6 >=1)) :
        print ("Yes")
    elif (node4 == 2) :
        if special_case() == 0 :
            print ("Yes")
        else :
            print ("No")
    else :
        print ("No")

Submission status: Accepted

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]
    Visited=[False]*n
    Visited[s]=True
    for v in Edges[s]:
        fr=v
        while fr!=t:
            Visited[fr]=True
            for to in Edges[fr]:
                if not Visited[to]:
                    fr=to
                    break
            if Visited[fr]:
                break
        if fr!=t:
            return 'Yes'
    return 'No'

print(main())

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
c = 0
d = 0
for _ in range(min(M, 1000)):
    a, b = map(int, input().split())
    d += a * 5 + b * 7
    c += a * 2 + b * 3
    d %= 100
    c %= 100
if c * 100 + d in [15, 238, 639, 1008, 1870, 2773, 3072, 3622, 4911, 4939, 5062, 5915, 6158, 6669, 7997, 8237, 8289, 9023, 9120, 9182, 9863, 9992]:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
#!/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")

Submission status: Accepted

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
    dst[b].append(a)

ddprint(dst)

x = [ len(z)%2 for z in dst ]
if 1 in x:
    print('No')
    exit()

s = sum([ len(z) - 2 for z in dst ])
if s >= 6:
  print('Yes')
  exit()
if s <= 2:
  print('No')
  exit()

# now s == 4
i4 = [ i for i in range(n) if len(dst[i]) >= 4 ]
ddprint('i4:')
ddprint(i4)
if len(i4) == 1:
  print('Yes')
  exit()

# 2 nodes with 4 arcs : A & B
#    1    8
#    |    |
# 2--+4--5+--7
#   A|    |B
#    3    6
# if all paths are A->B, no 3 circuits

a = i4[0]
b = i4[1]
alla2b = True
for i in range(4):
  prev = a
  x = dst[a][i]
  while x not in [a,b]:
    nxt = dst[x][1] if dst[x][0] == prev else dst[x][0]
    prev = x
    x = nxt
  ddprint('dai {} x now {}'.format(dst[a][i],x))
  if x == a:
      alla2b = False
      break

print('Yes' if not alla2b else 'No')

Submission status: Accepted

Solution code:
import sys

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

    for i in p[x]:
        bc = 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:
    y = d[x]
    if y % 2 != 0:
        r = False
        break
    if y >= 6:
        r = True
    if y >= 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: Accepted

Solution code:
N,M = map(int,input().split())
es = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

degs = [0] * N
for a,b in es:
    degs[a] += 1
    degs[b] += 1

if any(d%2 for d in degs):
    print('No')
    exit()
if any(d>=6 for d in degs):
    print('Yes')
    exit()

fours = degs.count(4)
if fours <= 1:
    print('No')
    exit()
elif fours >= 3:
    print('Yes')
    exit()

assert fours == 2
u = degs.index(4)
v = degs[u+1:].index(4) +u+1

g = [[] for i in range(N)]
for a,b in es:
    g[a].append(b)
    g[b].append(a)

for s in g[u]:
    visited = [0] * N
    stack = [s]
    first = True
    while stack:
        p = stack.pop()
        if p==u:
            print('Yes')
            exit()
        elif p==v:
            break
        visited[p] = 1
        for q in g[p]:
            if visited[q]: continue
            if first and q==u:
                first = False
                continue
            stack.append(q)
print('No')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

v = [0] * n
g = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    v[a] += 1
    v[b] += 1
    g[a].append(b)
    g[b].append(a)

for i in range(n):
    if v[i] % 2 == 1:
        print("No")
        exit()

v4 = 0
for i in range(n):
    if v[i] >= 6:
        print("Yes")
        exit()
    if v[i] == 4:
        v4 += 1

if v4 == 0:
    print("No")
    exit()
if v4 == 1:
    print("No")
    exit()
if v4 >= 3:
    print("Yes")
    exit()


memo = [0] * n
ord = [0] * n
lowlink = [0] * n
articulation = [0] * n

def dfs(v, p, k):
    memo[v] = 1
    ord[v] = k
    lowlink[v] = ord[v]
    isArticulation = False
    count = 0
    for nv in g[v]:
        if memo[nv] == 0:
            count += 1
            dfs(nv, v, k+1)
            lowlink[v] = min(lowlink[v], lowlink[nv])
            if p != -1 and ord[v] <= lowlink[nv]:
                isArticulation = True
        elif nv != p:
            lowlink[v] = min(lowlink[v], ord[nv])

    if p == -1 and count > 1:
        isArticulation = True
    if isArticulation:
        articulation[v] = 1

dfs(0, -1, 0)

count = 0
for i in range(n):
    if v[i] == 4 and articulation[i] == 1:
        count += 1

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

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  a, b = map(int, raw_input().split())
  E[a-1] += [b-1]
  E[b-1] += [a-1]

ok = True
for e in E:
  if len(e)%2!=0:
    ok = False
if not ok:
  print "No"
  exit(0)

ok = False
for e in E:
  if len(e)>=6:
    ok = True
if ok:
  print "Yes"
  exit(0)

c = 0
for e in E:
  if len(e)==4:
    c += 1
if c>=3:
  print "Yes"
  exit(0)
if c<=1:
  print "No"
  exit(0)

for i in range(len(E)):
  if len(E[i])==4:
    c = 0
    for v in E[i]:
      p = i
      while len(E[v])==2:
        if E[v][0]==p:
          p = v
          v = E[v][1]
        else:
          p = v
          v = E[v][0]
      if v==i:
        c += 1
    if c==2:
      print "Yes"
      exit(0)
    else:
      print "No"
      exit(0)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

graph = {}
for u in range(1, n + 1):
  graph[u] = set()
for i in range(m):
  u, v = map(int, input().split())
  graph[u].add(v)
  graph[v].add(u)
  
# check if has eulerian cycle
odd = 0
v6 = []
v4 = []
for u in range(1, n + 1): 
  if len(graph[u]) % 2 != 0: 
    odd += 1
    break
  elif len(graph[u]) >= 6:
    v6.append(u)
  elif len(graph[u]) == 4:
    v4.append(u)
if odd: 
  print('No')
else:
  # for has 3 cycles if any vertices has minimal six degree
  # or more than 2 vertices have 4 degrees
  if len(v6) > 0 or len(v4) > 2:
    print('Yes')
  # if vertices with 4 degrees less than 2
  elif len(v4) < 2:
    print('No')
  else:
    s = v4.pop()
    t = v4.pop()
    has_3_cycles= False
    for c in graph[s]:
      visited = {s, t}
      q = [c]
      while q:
        v = q.pop()
        if v in visited:
          continue
        visited.add(v)
        for u in graph[v]:
          if v != c and u == s:
            has_3_cycles = True
            break
          if u not in visited:
            q.append(u)
        if has_3_cycles:
          break
      if has_3_cycles:
        break
    print('Yes') if has_3_cycles else print('No')

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
E = [[] for i in range(n+1)]
used = [False] * (n + 1)
IN = [0] * (n + 1)

for i in range(m):
    a, b = [int(i) for i in input().split()]
    E[a].append(b)
    E[b].append(a)
    IN[a] += 1
    IN[b] += 1

cnt_4 = 0
cnt_6 = 0
v_4 = []
for j, i in enumerate(IN[1:]):
    if i % 2 == 1 or i == 0:
        print('No')
        exit()
    if i >= 4:
        cnt_4 += 1
        v_4.append(j + 1)
    if i >= 6:
        cnt_6 += 1

def dfs(p, v):
    if v == v_4[0]:
        return v_4[0]
    if v == v_4[1]:
        return v_4[1]

    for e in E[v]:
        if e == p:
            continue
        return dfs(v, e)

if cnt_4 > 2 or cnt_6 >= 1:
    print('Yes')
elif cnt_4 == 2:
    if all(dfs(v_4[0], e) == v_4[1] for e in E[v_4[0]]):
        print('No')
    else:
        print('Yes')

else:
    print('No')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import defaultdict

def main():
    N, M = LI()
    edges = defaultdict(list)
    for _ in range(M):
        a, b = LI_()
        edges[a].append(b)
        edges[b].append(a)
    quads = []
    large = 0
    for i, e in edges.items():
        c = len(e)
        if c % 2 == 1:
            return 'No'
        if c >= 6:
            large += 1
        if c == 4:
            quads.append(i)
    if large > 0:
        return 'Yes'
    if len(quads) > 2:
        return 'Yes'
    if len(quads) < 2:
        return 'No'
    for v in edges[quads[0]]:
        visited = [0] * N
        visited[quads[0]] = 1
        while v != quads[1]:
            visited[v] = 1
            for to in edges[v]:
                if visited[to] == 0:
                    v = to
                    break
            if visited[v] == 1:
                break
        if v != quads[1]:
            return 'Yes'

    return 'No'

print(main())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import defaultdict, deque

def main():
    N, M = LI()
    edges = defaultdict(set)
    for _ in range(M):
        a, b = LI_()
        edges[a].add(b)
        edges[b].add(a)
    quads = set()
    sixes = 0
    for i, e in edges.items():
        c = len(e)
        if c % 2 == 1:
            return False
        if c >= 6:
            sixes += 1
        if c == 4:
            quads.add(i)
    if sixes > 0:
        return True
    if len(quads) > 2:
        return True
    if len(quads) < 2:
        return False
    s = quads.pop()
    t = quads.pop()
    for v0 in edges[s]:
        q = deque([v0])
        visited = {s, t}
        while len(q) > 0:
            v = q.pop()
            for to in edges[v]:
                if v != v0 and to == s:
                    return True
                if to not in visited:
                    q.append(to)
                    visited.add(to)

    return False

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
V = []
D = 0
for i in range(N):
  if len(G[i]) % 2:
    print('No')
    break
  D = max(len(G[i]), D)
  if len(G[i]) == 4:
    V.append(i)
else:
  if D >= 6:
    print('Yes')
  elif len(V) != 2:
    print('Yes' if len(V) > 2 else 'No')
  else:
    s = V[0]
    for i in range(3):
      t = G[s].pop()
      G[t].pop(G[t].index(s))
      while t not in V:
        d = G[t].pop()
        G[d].pop(G[d].index(t))
        t = d
      if s == t:
        print('Yes')
        break
      else:
        s = t
    else:
      print('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
    que = deque()
    for v in G[s]:
        if v == t:
            continue
        u[v] = 1
        que.append(v)
        ok = 0
        while que:
            x = que.popleft()
            for y in G[x]:
                if y == s and x != v:
                    return 1
                if not u[y]:
                    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")