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

Solution (Python):
n,m=map(int,input().split())
p=[0]*n
edge=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  p[a]+=1
  p[b]+=1
  edge[a].append(b)
  edge[b].append(a)
for i in p:
  if i%2:exit(print("No"))
if p.count(6)>=1 or p.count(4)>=3:exit(print('Yes'))
if p.count(4)<2:exit(print('No'))
s,t=[i for i in range(n) if p[i]==4]
ss=[0]*n
ss[s]=1
stack=[s]
visited={s}
for i in stack:
  for j in edge[i]:
    if j in visited:continue
    ss[j]+=ss[i]
    if p[j]==4:continue
    visited.add(j)
    stack.append(j)
if ss[t]==2:print("Yes")
else:print("No")

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

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

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

    v=[]
    for i in range(n):
        le=len(l[i])
        if le%2!=0:
            print("No")
            return
        if le>=4:
            v.append(i)
    
    for item in v:
        if len(l[item])>=6:
            print("Yes")
            return
    ll=len(v)
    if ll<2:
        print("No")
        return
    elif ll>2:
        print("Yes")
        return

    s,e=v 
    for item in l[s]:
        p=s
        n=item

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

    print("No")

if __name__ == "__main__":
    main()

Solution (Python):
import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

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

odd=0
f=0
s=0
v=[]
for i in range(N):
    if len(edge[i])%2==1:
        odd+=1
    elif len(edge[i])==4:
        f+=1
        v.append(i)
    elif len(edge[i])>=6:
        s+=1

if odd>0:
    print("No")
else:
    if s>0:
        print("Yes")
    elif f>2:
        print("Yes")
    elif f!=2:
        print("No")
    else:
        start=v[0]
        ban=v[1]
        check=False
        def dfs(V,pv):
            global check
            if V==start and pv==-1:
                for i in edge[start]:
                    if i!=ban:
                        dfs(i,start)
            elif V==start:
                check=True
            else:
                for i in edge[V]:
                    if i!=ban and i!=pv:
                        dfs(i,V)
        dfs(start,-1)
        if check:
            print("Yes")
        else:
            print("No")

Solution (Python):
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
ls = []
for i,g in enumerate(graph):
  if len(g)%2:
    print("No")
    exit()
  if len(g) == 4:
    jdg += 1
    ls.append(i)
  elif len(g) >= 6:
    jdg += 3
if jdg >= 3:
  print("Yes")
elif jdg == 2:
  start,goal = ls
  stack = [start]
  vis = [0]*(n+1)
  vis[start] = 1
  vis[goal] = 2
  jdg2 = 0
  while stack:
    x = stack.pop()
    for y in graph[x]:
      if vis[y] == 0:
        vis[y] = 1
        stack.append(y)
      elif vis[y] == 2:
        jdg2 += 1
  if jdg2 == 4:
    print("No")
  else:
    print("Yes")
else:
  print("No")

Solution (Python):
import sys
input = sys.stdin.readline

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


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

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

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

Solution (Python):


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

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

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


    seen = [False] * n
    prev = [None] * n
    cs = []
    count = 0
    done = True
    





    for start in range(n):
        if seen[start]:
            continue
        q = [start]
        current_seen = [False] * n
        update = False
        while q:
            u = q.pop()
            current_seen[u] = True
            for v in ns[u]:
                if used[u,v] or prev[u]==v:
                    continue
                prev[v] = u
                if current_seen[v]:
                    
                    count += 1
                    c = set()
                    tmp = v
                    while tmp not in c:
                        c.add(tmp)
                        used[tmp, prev[tmp]] = used[prev[tmp], tmp] = True
                        tmp = prev[tmp]
                    cs.append(c)
                    for u in c:
                        seen[u] = True
                    update = True
                    break
                q.append(v)
            if update:
                break
        if not update:
            print("No")
            return 
    if sum(seen)<n:
        print("No")
        return
    def sub(cs):
        if len(cs)==1:
            return "No"
        elif len(cs)==2:
            if len(set(cs[0] & cs[1]))>=3:
                return "Yes"
            else:
                return "No"
        else :
            return "Yes"
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    if done:
        print(sub(cs))
    
hoge()

Solution (Python):


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


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

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


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


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

    def sub(cs):
        if len(cs)==1:
            return "No"
        elif len(cs)==2:
            if len(set(cs[0] & cs[1]))>=3:
                return "Yes"
            else:
                return "No"
        else :
            return "Yes"
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    if done:
        print(sub(cs))
    
hoge()

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

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

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

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

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

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

Solution (Python):
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')

Solution (Python):
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')

Solution (Python):

"""

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

    

    for i in lis[x]:

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

        while len(q) > 0:

            

            now = q.popleft()

            for j in lis[now]:
                
                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")

Solution (Python):
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')

Solution (Python):
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))

Solution (Python):
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")

Solution (Python):
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():
    
    if any(x&1 for x in deg):
        return False
    cycle = 0
    
    
    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)

Solution (Python):
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)



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






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)

Solution (Python):
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)

for i, line in enumerate(edge):
    o = len(line)
    order[o] += 1
    if o % 2 != 0:
        print("No")
        exit()
    if o >= 4:
        index = i


if max(order[6:]) > 0:
    print("Yes")
    exit()


if order[4] <= 1:
    print("No")
    exit()

elif order[4] >= 3:
    print("Yes")
    exit()

else:
    ret = find_single_self_loop(index, -1, index)
    if ret:
        print("Yes")
    else:
        print("No")

Solution (Python):
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]

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]:
    
    if f(x):
        print('Yes')
        sys.exit()
print('No')

Solution (Python):
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')

Solution (Python):
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:
        
        
        return True

    
    vertexes = [v for v in range(N) if dims[v] == 4]

    if len(vertexes) >= 3:
        
        return True

    if len(vertexes) == 2:
        
        
        
        
        

        
        
        
        return has_circuit(g, vertexes[0], vertexes[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')

Solution (Python):

def special_case() :
    
    
    
    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)]

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)



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

Solution (Python):
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())

Solution (Python):
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")

Solution (Python):





















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

Solution (Python):
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()


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









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

Solution (Python):
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")

Solution (Python):
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')

Solution (Python):
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")