Problem:


Score : 800 points

Problem Statement

You are given a simple connected undirected graph consisting of N vertices and M edges.
The vertices are numbered 1 to N, and the edges are numbered 1 to M.

Edge i connects Vertex a_i and b_i bidirectionally.

Determine if three circuits (see Notes) can be formed using each of the edges exactly once.

Notes

A circuit is a cycle allowing repetitions of vertices but not edges.

Constraints

All values in input are integers.

1 \leq N,M \leq 10^{5}

1 \leq a_i, b_i \leq N

The given graph is simple and connected.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
:
a_M b_M

Output

If three circuits can be formed using each of the edges exactly once, print Yes; if they cannot, print No.

Sample Input 1

7 9
1 2
1 3
2 3
1 4
1 5
4 5
1 6
1 7
6 7

Sample Output 1

Yes

Three circuits can be formed using each of the edges exactly once, as follows:

Sample Input 2

3 3
1 2
2 3
3 1

Sample Output 2

No

Three circuits are needed.

Sample Input 3

18 27
17 7
12 15
18 17
13 18
13 6
5 7
7 1
14 5
15 11
7 6
1 9
5 4
18 16
4 6
7 2
7 11
6 3
12 14
5 2
10 5
7 8
10 15
3 15
9 8
7 15
5 16
18 15

Sample Output 3

Yes



Sample input:
7 9
1 2
1 3
2 3
1 4
1 5
4 5
1 6
1 7
6 7


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
counter = [-2] * n
for edge in edges:
    counter[edge[0] - 1] += 1
    counter[edge[1] - 1] += 1
sol = 0
for c in counter:
    if c % 2:
        print('No')
        break
else:
    if sum(counter) >= 4:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

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

parities = [deg % 2 for deg in degs]
if sum(parities):
    print('No')
else:
    deg4s = [deg >= 4 for deg in degs]
    if deg4s.count(True) >= 2:
        print('Yes')
    else:
        deg6s = [deg >= 6 for deg in degs]
        if any(deg6s):
            print('Yes')
        else:
            print('No')

Submission status: Wrong Answer

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

N,M =[int(i)for i in input().split()]
lis = [[int(i)-1 for i in input().split()]for _ in range(M)]
adj =[0]*N
for i,j in lis:
    adj[i]+=1
    adj[j]+=1

count = 0
s= True
for i in adj:
    if i%2==1:
        s = False
        print("No")
        break
    elif i == 4:
        count += 1
    elif i == 6:
        count = 3


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

Submission status: Wrong Answer

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

dp = [0 for _ in range(N + 1)]
for i, j in zip(a, b):
    dp[i] += 1
    dp[j] += 1
ans = 'Yes' if all(dp[i] % 2 == 0 for i in range(1, N + 1)) and (max(dp) >= 6 or sum(dp[i] >= 4 for i in range(1, N + 1)) >= 2) else 'No'
print(ans)

Submission status: Wrong Answer

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

peaks = {}
for p in ppp:
    if p[0] in peaks:
        peaks[p[0]].append(p[1])
    else:
        peaks[p[0]] = [p[1]]

    if p[1] in peaks:
        peaks[p[1]].append(p[0])
    else:
        peaks[p[1]] = [p[0]]

isNG = False
counter = 0
for k, v in sorted(peaks.items(), key=lambda x: len(x[1]), reverse=True):
    if len(v) == 0:
        continue
    moved = v[0]
    peaks[k].remove(moved)
    peaks[moved].remove(k)
    while moved != k:
        if len(peaks[moved]) == 0:
            isNG = True
            break
        mov = peaks[moved][0]
        peaks[moved].remove(mov)
        peaks[mov].remove(moved)
        moved = mov
    counter += 1
    if counter == 3:
        for k,v in peaks.items():
            if len(v) != 0:
                isNG = True
                break
        break
    if isNG:
        break
if isNG or counter != 3:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

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, 0])
  G[b - 1].append([a - 1, 0])
s = -1
for i, v in enumerate(G):
  if len(v) % 2:
    print('No')
    break
  if len(v) >= 4:
    s = i
else:
  cnt = 0
  visited = [0] * N
  pre = [N] * N
  if s < 0:
    print('No')
  else:
    while True:
      for i, e in enumerate(G[s]):
        if e[1] == 0:
          G[s][i][1] = 1
          if visited[e[0]] == 1:
            while s != e[0]:
              visited[s] = 0
              p = pre[s]
              pre[s] = N
              s = p
            cnt += 1
          else:
            visited[s] = 1
            pre[e[0]] = s
            s = e[0]
          break
      else:
        break
    print('Yes' if cnt >= 3 else 'No')

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if m >= n+2:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:

N,M=list(map(int,input().split()))
path=[0 for i in range(N)]
for i in range(M):
    a,b=list(map(int,input().split()))
    path[a-1]+=1
    path[b-1]+=1
count=0
flg=True

for p in path:
    if p%2!=0:
        flg=False
        break
    if p>=6:
        count+=2
    elif p==4:
        count+=1
if count>=2 and flg:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = [0] * N
for _ in range(M):
    a, b = map(int, input().split())
    X[a-1] += 1
    X[b-1] += 1
    
for x in X:
    if x % 2 > 0:
        print("No")
        break
else:
    c = 0
    for x in X:
        if x == 4:
            c += 1
        if x >= 6:
            c = 2
            break
    if c >= 2:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())

def getlist():
    return list(map(int, input().split()))

from collections import Counter

n,m = getlist()
lis = []
for i in range(m):
    lis += getlist()

c = Counter(lis)

flag = True
buffer = 0
for k, v in c.items():
    if v % 2 != 0:
        flag = False
    else:
        buffer += v//2 - 1

if flag and (buffer >= 2):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
degree = [0 for i in range(N)]
for i in range(M):
	a,b = map(int,input().split())
	degree[a-1] += 1
	degree[b-1] += 1

cnt = 0
for deg in degree:
	if deg % 2 == 1:
		print("No")
		exit()
	else:
		if deg >= 6:
			print("Yes")
			exit()
		elif deg == 4:
			cnt += 1
if cnt >= 3:
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = list()
b = list()
for i in range(m):
    an, bn = map(int, input().split())
    a.append(an)
    b.append(bn)

count = 0

for i in range(0,m-1):
    for k in range(1,m-1-i):
        if a[i] == a[i+k]:
            c = b[i]
            d = b[i+k]
            for j in range(m):
                if (a[j] == c and b[j] == d) or (a[j] == d and b[j] == c) :
                    count += 1

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = [0 for i in range(n)]
c = 0
for i in range(m):
        a,b = map(int,input().split())
        s[a-1] += 1
        s[b-1] += 1

if max(s) < 6:
        c = 1
        print("No")
else:
        for i in range(n):
                if s[i] % 2 != 0:
                        print("No")
                        c = 1
                        break

if c == 0:
        print("Yes")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

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

    if all(d%2==0 for d in D.values()) and (sum(1 for d in D.values() if d>=4)>=2 or sum(1 for d in D.values() if d>=6)>=1):
        res = 'Yes'
    else:
        res = 'No'
    return str(res)
if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

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()
    visited = set()
    q = [s]
    while q:
        v = q.pop()
        if v == t:
            continue
        if v == s:
            if s in visited:
                return True
        elif v in visited:
            continue
        visited.add(v)
        q.extend(u for u in links[v] if u not in visited)
    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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

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

    if all(d%2==0 for d in D.values()) and (sum(1 for d in D.values() if d>=4)>=2 or sum(1 for d in D.values() if d>=6)>=1):
        res = 'YES'
    else:
        res = 'NO'
    return str(res)
if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

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

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

count_sum = 0
count4 = 0
count6 = 0
for temp in count:
    if temp % 2 == 1:
        print("No")
        exit()
    else:
        if temp >= 4:
            count4 += 1
        if temp >= 6:
            count6 += 1
        count_sum += temp

if count4 >= 3 or count6 >= 1:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = []
t = []
c = 0
for i in range(m):
        s = s + list(map(int,input().split()))
for i in range(n):
        t.append(s.count(i+1))

if max(t) < 6:
        c = 1
        print("No")
else:
        for i in range(n):
                if t[i] % 2 != 0:
                        print("No")
                        c = 1
                        break

if c == 0:
        print("Yes")

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
l = [0]*(n+1)
for _ in range(m):
  a,b = map(int, input().split())
  l[a] += 1
  l[b] += 1
even = 0
up6 = 0
up4 = 0
for i in l:
  if i%2==0:
    even += 1
  if i >= 6:
    up6 += 1
  if i >= 4:
    up4 += 1
if even == n+1 and (up6 >= 1 or up4 >= 3):
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
counter = [-2] * n
for i in range(m):
    counter[edge[i][0] - 1] += 1
    counter[edge[i][1] - 1] += 1
sol = 0
for c in counter:
    if c % 2:
        sol = -1
        break
    sol += c
if sol >= 4:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

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

for i in range(N):
    if X[i] % 2:
        print("No")
        break
else:
    if sum(X) - 2 * N >= 4:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Edge = [0] * N
for _ in range(M):
    a, b = map(int, input().split())
    Edge[a - 1] += 1
    Edge[b - 1] += 1
if any([i%2 == 1 for i in Edge]):
    print('No')
elif sum([i for i in Edge if i > 2]) < 6:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
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)
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
print("Yes" if ok else "No")

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = list()
b = list()
for i in range(m):
    an, bn = map(int, input().split())
    a.append(an)
    b.append(bn)

count = 0

for i in range(0,m-1):
    for k in range(m-1-i):
        if a[i] == a[i+k]:
            c = b[i]
            d = b[i+k]
            for j in range(m):
                if a[j] == c & b[j] == d:
                    count += 1

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

Submission status: Wrong Answer

Solution code:
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)
C = [0]*4
for i in range(N):
    C[min(3, len(G[i])//2)] += 1
ok = 1
if C[1] == N or (C[1] == N-1 and C[2] == 1):
    ok = 0
print("Yes" if ok else "No")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
counter = [0] * n
for i in range(m):
    counter[edge[i][0] - 1] += 1
    counter[edge[i][1] - 1] += 1
sol = 0
for c in counter:
    if c % 2:
        sol = -1
        break
    sol += max(0, c - 2)
if sol >= 4:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, input().split())
G = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    cnt[a-1]+=1
    cnt[b-1]+=1
if any(cnt[i]%2 == 1 for i in range(n)):
    print('No')
    sys.exit()
c = cnt.count(4)
if any(cnt[i]>=6 for i in range(n)) or c>=3:
    print('Yes')
    sys.exit()
if c<1:
    print('No')
    sys.exit()
v = cnt.index(4)
used = [False]*n
for v0 in G[v]:
    now = v0
    used[v0] = True
    while True:
        for nv in G[now]:
            if used[nv]:
                continue
            now = nv
            used[now] = True
        if now == v0:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, input().split())
G = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    cnt[a-1]+=1
    cnt[b-1]+=1
if any(cnt[i]%2 == 1 for i in range(n)):
    print('No')
    sys.exit()
c = cnt.count(4)
if any(cnt[i]>=6 for i in range(n)) or c>=3:
    print('Yes')
    sys.exit()
if c<1:
    print('No')
    sys.exit()
v = cnt.index(4)
used = [False]*n
for v0 in G[v]:
    now = v0
    used[v0] = True
    while True:
        for nv in G[now]:
            if used[nv]:
                continue
            now = nv
        if now == v0:
            print('Yes')
            sys.exit()
        if cnt[now] == 4:
            break
print('No')

Submission status: Time Limit Exceeded

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] :
        p = i
        while (check[p]==2) :
            t1, t2 = edge[p]
            if t1 == st :
                p = t2
            else: 
                p = t1
        if p == 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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

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

    E = defaultdict(int)
    X = list()
    for a,d in D.items():
        if d%2==0:
            if d >= 6:
                E[6] += 1
            elif d == 4:
                E[4] += 1
                X.append(a)
            else:
                E[d] += 1
        else:
            E[1] += 1

    if E[1]==0 and (E[6]>=1 or E[4]>=3):
        res = 'Yes'
    elif E[4]==2:
        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]):
            res = 'No'
        else:
            res = 'Yes'
    else:
        res = 'No'
    return str(res)
if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

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

    E = defaultdict(int)
    for d in D.values():
        E[d] += 1



    if all(k%2==0 for k in E.keys()) and (sum(E[k] for k in E.keys() if k >=6)>=1 or E[4]>=3):
        res = 'Yes'
    elif E[4]==2:
        x, y = [a for a,d in D.items() if d == 4]
        q = set((y,))
        R = set()
        while q:
            z = q.pop()
            if z != x:
                R.add(z)
                q |= set(F[z])-R
        if set(F[x])&R == set(F[x]):
            res = 'No'
        else:
            res = 'Yes'
    else:
        res = 'No'
    return str(res)
if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

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()
    visited = set()
    q = [s]
    while q:
        v = q.pop()
        if v == t:
            continue
        if v == s:
            if s in visited:
                return True
        elif v in visited:
            continue
        visited.add(s)
        q.extend(u for u in links[v] if u not in visited)
    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:
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")

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    #n = int(input())
    #l = list(map(int, input().split()))
    '''
    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:#euler
            print("No")
            return
        if le>=4:
            v.append(i)
    #e>6>4
    for item in v:
        if len(l[item])>=6:
            print("Yes")
            return
    ll=len(v)
    if ll<2:#4*1~0
        print("No")
        return
    elif ll>2:
        print("Yes")
        return

    s,e=v #4*2
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# AGC032C

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")
            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"
    #     u2s = defaultdict(set)
    #     nns = defaultdict(set) # i番目のサイクルと重なるサイクル
    #     for i,s in enumerate(cs):
    #         for u in s:
    #             nns[i] |= u2s[u]
    #             u2s[u].add(i)
    #     for i,s in nns.items():
    #         for j in s:
    #             nns[j].add(i)
    #     count = 0
    # #     print(u2s)
    # #     print(nns)
    #     seen = [False] * len(cs)
    #     for start in range(len(cs)):
    #         if seen[start]:
    #             continue
    #         q = [start]
    #         seen[start] = True
    #         while q:
    #             u = q.pop()
    #             for v in nns[u]:
    #                 if not seen[v]:
    #                     q.append(v)
    #                     seen[v] = True
    #         count += 1
    #     if count<=3:
    #         return "Yes"
    #     else:
    #         return "No"
    if done:
        print(sub(cs))
    #     print("Yes")
hoge()

Submission status: Accepted

Solution code:
# AGC032C

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:
    #         print(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"
    #     u2s = defaultdict(set)
    #     nns = defaultdict(set) # i番目のサイクルと重なるサイクル
    #     for i,s in enumerate(cs):
    #         for u in s:
    #             nns[i] |= u2s[u]
    #             u2s[u].add(i)
    #     for i,s in nns.items():
    #         for j in s:
    #             nns[j].add(i)
    #     count = 0
    # #     print(u2s)
    # #     print(nns)
    #     seen = [False] * len(cs)
    #     for start in range(len(cs)):
    #         if seen[start]:
    #             continue
    #         q = [start]
    #         seen[start] = True
    #         while q:
    #             u = q.pop()
    #             for v in nns[u]:
    #                 if not seen[v]:
    #                     q.append(v)
    #                     seen[v] = True
    #         count += 1
    #     if count<=3:
    #         return "Yes"
    #     else:
    #         return "No"
    if done:
        print(sub(cs))
    #     print("Yes")
hoge()

Submission status: Accepted

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