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

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

    six = 0
    four = 0
    for a in d:
        if a & 1:
            return False
        if a >= 4:
            four += 1
        if a >= 6:
            six += 1

    return four >= 2 or six >= 1


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

Submission status: Wrong Answer

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

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

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

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

check = [False] * N

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

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

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

    return ret

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

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
import sys
# from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

ans = "Yes"
cnts = [0] * N
for ai, bi in ab:
    cnts[ai - 1] += 1
    cnts[bi - 1] += 1

# if cnts.count(6) + cnts.count(4) + cnts.count(2) == N: print("Yes")

for cnti in cnts:
    if cnti % 2 or cnti > 6:
        print("No")
        break
else: print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

n,m = map(int,input().split())
cnt = [0] * n
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    cnt[a] += 1
    cnt[b] += 1
cnt = sorted(cnt, reverse = True)

odd = 0
even = 0
two = 0
g = gb(cnt)
for k,v in g:
    vv =len(list(v))
    if k == 2:
        two += 1
        continue
    if vv % 2 == 0:
        even += 1
    else:
        odd += 1
if odd <= 1:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
degree = [0 for i in range(N)]
edge = [[] for i in range(N)]
for i in range(M):
	a,b = map(int,input().split())
	degree[a-1] += 1
	degree[b-1] += 1
	edge[a-1].append(b-1)
	edge[b-1].append(a-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")
	exit()

search = [i for i in range(N) if degree[i] == 2]
terminal = [i for i in range(N) if degree[i] > 2]
current = []
goal = []
while len(search) > 0:
	start = search.pop(0)
	current.append(start)
	while len(goal) < 2:
		node = current.pop(0)
		a,b = edge[node][0], edge[node][1]
		if a in terminal:
			goal.append(a)
		else:
			if a in search:
				search.remove(a)
			current.append(a)
		if b in terminal:
			goal.append(b)
		else:
			if b in search:
				search.remove(b)
			current.append(b)
	if goal[0] == goal[1]:
		print("Yes")
		exit()
	curent = []
	goal = []
print("No")

Submission status: Wrong Answer

Solution code:
#!venv/bin/python

import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 

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

def main():
    circle_num = 0
    while circle_num <= 3:
        start = None
        for b in BRIDGE:
            if BRIDGE[b]:
                start = b
                break
        else:
            #print("bridge not found")
            break
        #print("start: " + str(start))
        if circle_find(start):
            circle_num += 1
        else:
            #print("circle not found")
            break
        #print(BRIDGE)
    #print(BRIDGE)

    if circle_num == 3:
        has_bridge = False
        for b in BRIDGE:
            if BRIDGE[b]:
                has_bridge = True
                break
        if not has_bridge:
            print("Yes")
            return
    print("No")
    

def circle_find(start):
    next = now = start
    while True:
        now = next
        if start in BRIDGE[now]:
            if not (len(BRIDGE[start]) >= 3 and len(BRIDGE[now])):
                next = start
                #print("next: " + str(next))
                BRIDGE[now].remove(next)
                BRIDGE[next].remove(now)
                return True
            else:
                next = None
                for n in BRIDGE[now]:
                    if n != start:
                        next = n
                        break
                else:
                    next = start
                    BRIDGE[now].remove(next)
                    BRIDGE[next].remove(now)
                    return True
                BRIDGE[now].remove(next)
                BRIDGE[next].remove(now)
                continue
        if not BRIDGE[now]:
            return False
        next = BRIDGE[now][0]
        BRIDGE[now].remove(next)
        BRIDGE[next].remove(now)


main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5 * 2)

loop_count = 0

def dfs(graph, path, ps):
    global loop_count
    a = path[-1]
    nexts = list(graph[path[-1]])
    for nex in nexts:
        try:
            graph[a].remove(nex)
            graph[nex].remove(a)
        except KeyError:
            continue
        if nex in ps:
            loop_count += 1
            ps.remove(path.pop())
            return nex
        else:
            path.append(nex)
            ps.add(nex)
            ret = dfs(graph, path, ps)
            if ret is None:
                return
            if ret != a:
                ps.remove(path.pop())
                return ret


def main():
    n, m = map(int, raw_input().split())
    graph = {}
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        if a not in graph:
            graph[a] = set()
        if b not in graph:
            graph[b] = set()
        graph[a].add(b)
        graph[b].add(a)
    for g in graph:
        if graph[g]:
            dfs(graph, [g], {g})
    if loop_count < 3 or any(len(g) > 0 for g in graph.itervalues()):
        print 'No'
    else:
        print 'Yes'


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

N,M = map(int,input().split())
from collections import defaultdict
d = defaultdict(lambda:[])
ed = {}
for i in range(M):
    a,b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    k = [a,b]
    k.sort()
    k = (k[0],k[1])
    ed[k] = i

u = UnionFind(M)

for x in d:
    if len(d[x])==2:
        k1 = (min(x,d[x][0]),max(x,d[x][0]))
        k2 = (min(x,d[x][1]),max(x,d[x][1]))
        u.union(ed[k1],ed[k2])

ans = []
for i in range(M):
    ans.append(u.find(i))

ans = set(ans)

if len(ans)==3:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
def string(a,b):
	return (str(a)+"."+str(b))
def bfs(s):
	stk=[]
	stk.append(s)
	while len(stk)>0:
		s=stk[0]
		# print(stk)
		stk.remove(s)
		# print(s)
		for i in range(len(adj[s])):
			k=adj[s][i]
			if k==1:
				continue
			if parent[k]==0:
				parent[k]=s
				stk.append(k)
			else:
				if ct[0]>0:
					lst=[string(s,k)]
					if lst[0] not in mp:
						# print(s,k)
						chk={}
						p1=s
						while(parent[p1]!=0):
							# print("dd")
							lst.append(string(p1,parent[p1]))
							if lst[-1] not in mp:
								chk[parent[p1]]=1
								p1=parent[p1]
							else:
								chk={}
								break
						# print(lst)
						if len(chk)>0:
							p2=k
							while(parent[p2]!=0):
								# print("dff")
								lst.append(string(p2,parent[p2]))
								if lst[-1] not in mp:
									if parent[p2] in chk:
										break
									else:
										p2=parent[p2]
								else:
									lst=[]
									break
						# print(lst)
						if len(lst)>0:
							while(len(lst)>0):
								mp[lst[-1]]=1
								mp[lst[-1][::-1]]=1
								lst.pop()
							ct[0]-=1


n,m=map(int,input().split())
adj=[0]*(n+1)
for i in range(n+1):
	adj[i]=[]
for j in range(m):
	x,y=map(int,input().split())
	adj[x].append(y)
	adj[y].append(x)
parent=[0]*(n+1)
ct=[3]*1
mp={}
bfs(1)
if ct[0]==0:
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
import sys
# from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

ans = "Yes"
cnts = [0] * N
for ai, bi in ab:
    cnts[ai - 1] += 1
    cnts[bi - 1] += 1

# if cnts.count(6) + cnts.count(4) + cnts.count(2) == N: print("Yes")

for cnti in cnts:
    if cnti % 2:
        print("No")
        break
else: print("Yes")

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
connect = [list(map(int,input().split())) for _ in range(M)]

bucket = [0]*N
for a,b in connect:
    bucket[a-1] += 1
    bucket[b-1] += 1
    
isOdd = False
SixEdge = False
FourEdgeCnt = 0
edgeEven = 0

for n in bucket:
    if n %2:
        isOdd = True
        break
    if n>=6:
        SixEdge = True
    if n>=4:
        FourEdgeCnt +=1
        edgeEven += (n-2)//2

if (not isOdd) and (SixEdge or FourEdgeCnt>=2):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
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
for i in IN[1:]:
    if i % 2 == 1 or i == 0:
        print('No')
        exit()
    if i >= 4:
        cnt_4 += 1
    if i >= 6:
        cnt_6 += 1

if cnt_4 >= 2 or cnt_6 >= 1:
    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 = -1
        break


if s:
    if count == -1:
        print("Yes")
    else:
        print("No")

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
  clear = [0] * 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:
        clear[s] = 1
        s = -1
        for i in range(N):
          if clear[i] == 0:
            for e in G[i]:
              if e[1] == 0:
                s = i
                break
            else:
              clear[i] = 1
          if s > 0:
            break
        else:
          break
    print('Yes' if cnt >= 3 else 'No')

Submission status: Wrong Answer

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

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

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

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

check = [False] * N

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

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

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

    return ret

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]
connect = [set() for _ in range(n)]
for a, b in edge:
    a -= 1
    b -= 1
    connect[a].add(b)
    connect[b].add(a)
def search(cur, start):
    if start in connect[cur]:
        connect[cur].discard(start)
        connect[start].discard(cur)
    elif connect[cur] == set():
        print('No')
        exit()
    else:
        x = connect[cur].pop()
        connect[x].discard(cur)
        search(x, start)
for _ in range(3):
    # check not all set
    allset = True
    for s in connect:
        if s != set():
            allset = False
    if allset:
        print('No')
        exit()
    for a, b in edge:
        a -= 1
        b -= 1
        if a in connect[b]:
            connect[a].discard(b)
            connect[b].discard(a)
            search(a, b)
            break
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5 * 2)

loop_count = 0

def dfs(graph, path, ps):
    global loop_count
    a = path[-1]
    nexts = list(graph[path[-1]])
    for nex in nexts:
        try:
            graph[a].remove(nex)
            graph[nex].remove(a)
        except KeyError:
            continue
        if nex in ps:
            loop_count += 1
            path.pop()
            return nex
        else:
            path.append(nex)
            ps.add(nex)
            ret = dfs(graph, path, ps)
            if ret is None:
                return
            if ret != a:
                path.pop()
                ps.remove(nex)
                return ret


def main():
    n, m = map(int, raw_input().split())
    graph = {}
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        if a not in graph:
            graph[a] = set()
        if b not in graph:
            graph[b] = set()
        graph[a].add(b)
        graph[b].add(a)
    for g in graph:
        if graph[g]:
            dfs(graph, [g], {g})
    if loop_count < 3 or any(len(g) > 0 for g in graph.itervalues()):
        print 'No'
    else:
        print 'Yes'


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]
connect = [set() for _ in range(n)]
for a, b in edge:
    a -= 1
    b -= 1
    connect[a].add(b)
    connect[b].add(a)
def search(cur, start):
    if start in connect[cur]:
        connect[cur].discard(start)
        connect[start].discard(cur)
    elif connect[cur] == set():
        print('No')
        exit()
    else:
        x = connect[cur].pop()
        connect[x].discard(cur)
        search(x, start)
for _ in range(3):
    # check not all set
    allset = True
    for s in connect:
        if s != set():
            allset = False
    if allset:
        print('No')
        exit()
    for a, b in edge:
        a -= 1
        b -= 1
        if a in connect[b]:
            connect[a].discard(b)
            connect[b].discard(a)
            search(a, b)
            break
print('Yes')

Submission status: Wrong Answer

Solution code:
print("No")

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
import sys
# from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

ans = "Yes"
cnts = [0] * N
for ai, bi in ab:
    cnts[ai - 1] += 1
    cnts[bi - 1] += 1

if cnts.count(6) == 1 and cnts.count(2) == N - 1: print("Yes")
elif cnts.count(4) == 2 and cnts.count(2) == N - 2: print("Yes")
elif cnts.count(4) == 1 and cnts.count(3) == 2 and cnts.count(2) == N - 3: print("Yes")
elif cnts.count(3) == 4 and cnts.count(2) == N - 4: 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:
from collections import Counter

# import sys
# sys.setrecursionlimit(200000)

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

choten = [0 for _ in range(N)]

for _ in range(M):
    a, b = list(map(int, input().split(" ")))
    choten[a - 1] += 1
    choten[b - 1] += 1

if min(choten) <= 1:
    print("No")
    exit()

c = Counter(choten)
res = sorted(c.most_common(), key=lambda x: -x[0])


if res[0][0] >= 6:
    print("Yes")
elif res[0][0] == 4:
    if res[0][1] >= 2:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
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
for i in IN:
    if i % 2 == 1:
        print('No')
        exit()
    if i >= 4:
        cnt_4 += 1
    if i >= 6:
        cnt_6 += 1

if cnt_4 >= 2 or cnt_6 >= 1:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
print("NO")

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 isNG:
        break

for k,v in peaks.items():
    if len(v) != 0:
        isNG = True
        break
if isNG or counter < 3:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5 * 2)

loop_count = 0

def dfs(graph, path):
    global loop_count
    a = path[-1]
    nexts = list(graph[path[-1]])
    for nex in nexts:
        try:
            graph[a].remove(nex)
            graph[nex].remove(a)
        except KeyError:
            continue
        if nex in path:
            loop_count += 1
            path.pop()
            return nex
        else:
            path.append(nex)
            ret = dfs(graph, path)
            if ret is None:
                return
            if ret != a:
                path.pop()
                return ret


def main():
    n, m = map(int, raw_input().split())
    graph = {}
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        if a not in graph:
            graph[a] = set()
        if b not in graph:
            graph[b] = set()
        graph[a].add(b)
        graph[b].add(a)
    for g in graph:
        if graph[g]:
            dfs(graph, [g])
    if loop_count < 3 or any(len(g) > 0 for g in graph.itervalues()):
        print 'No'
    else:
        print 'Yes'


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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
for i in IN:
    if i % 2 == 1:
        print('No')
        exit()
    if i == 4:
        cnt_4 += 1
    if i == 6:
        cnt_6 += 1

if cnt_4 >= 2 or cnt_6 >= 1:
    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 sum(dp[i] % 2 == 1 for i in range(1, N + 1)) <= 6 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())
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])
for i, v in enumerate(G):
  if len(v) % 2:
    print('No')
    break
else:
  cnt = 0
  visited = [0] * N
  pre = [N] * N
  clear = [0] * N
  s = 0
  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:
      clear[s] = 1
      s = -1
      for i in range(N):
        if clear[i] == 0:
          for e in G[i]:
            if e[1] == 0:
              s = i
              break
          else:
            clear[i] = 1
        if s > 0:
          break
      else:
        break
  print('Yes' if cnt >= 3 else 'No')

Submission status: Wrong Answer

Solution code:
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
for i in IN:
    if i % 2 == 1:
        print('No')
        exit()
    if i == 4:
        cnt_4 += 1
    if i >= 6:
        cnt_6 += 1

if cnt_4 >= 2 or cnt_6 >= 1:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

def main():
    N, M = LI()
    cnt = [0] * N
    for _ in range(M):
        a, b = LI_()
        cnt[a] += 1
        cnt[b] += 1
    loops = 1
    for c in cnt:
        if c % 2 == 1:
            loops = -1
            break
        loops += (c // 2) - 1
    ans = 'Yes' if loops == 3 else 'No'

    return ans

print(main())

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])
for i, v in enumerate(G):
  if len(v) % 2:
    print('No')
    break
else:
  cnt = 0
  visited = [0] * N
  pre = [N] * N
  clear = [0] * N
  s = 0
  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:
      clear[s] = 1
      s = -1
      for i in range(N):
        if clear[i] == 0:
          for e in G[i]:
            if e[1] == 0:
              s = i
              break
          else:
            clear[i] = 1
          if s > 0:
            break
      else:
        break
  print('Yes' if cnt >= 3 else '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
print("No")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def main():
    N, M = LI()
    cnt = [0] * N
    for _ in range(M):
        a, b = LI_()
        cnt[a] += 1
        cnt[b] += 1
    loops = 1
    for c in cnt:
        if c % 2 == 1:
            loops = -1
            break
        loops += (c // 2) - 1
    ans = 'Yes' if loops >= 3 else 'No'

    return ans

print(main())

Submission status: Wrong Answer

Solution code:
#!venv/bin/python

import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 

N, M = [int(x) for x in input().split()]
BRIDGE = defaultdict(list)
for i in range(M):
    a, b = [int(x) for x in input().split()]
    BRIDGE[a].append(b)
    BRIDGE[b].append(a)
USED = defaultdict(dict)

def main():
    circle_num = 0
    while circle_num <= 3:
        start = None
        for b in BRIDGE:
            if BRIDGE[b]:
                start = b
                break
        else:
            #print("bridge not found")
            break
        #print("start: " + str(start))
        if circle_find(start):
            circle_num += 1
        else:
            #print("circle not found")
            break
        #print(BRIDGE)
    #print(BRIDGE)

    if circle_num == 3:
        has_bridge = False
        for b in BRIDGE:
            if BRIDGE[b]:
                has_bridge = True
                break
        if not has_bridge:
            print("Yes")
            return;
    print("No")
    

def circle_find(start):
    next = now = start
    while True:
        now = next
        if start in BRIDGE[now]:
            next = start
            #print("next: " + str(next))
            BRIDGE[now].remove(next)
            BRIDGE[next].remove(now)
            return True
        if not BRIDGE[now]:
            return False
        next = BRIDGE[now][0]
        BRIDGE[now].remove(next)
        BRIDGE[next].remove(now)


main()

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
AB = list(list(map(int, input().split())) for _ in range(M))

print('Yes')

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