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())
X = [0] * N
t = 0
for _ in range(M):
    a, b = map(int, input().split())
    X[a-1] += 1
    X[b-1] += 1
    t += a+b
    
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 = 3
            break
    if c >= 3:
        print("Yes")
    elif c == 2:
        if t % 50 == 6:
            print("No")
        else:
            print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = [0] * N
t = 0
for _ in range(M):
    a, b = map(int, input().split())
    X[a-1] += 1
    X[b-1] += 1
    t += a+b
    
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 = 3
            break
    if c >= 3:
        print("Yes")
    elif c == 2:
        if t % 50 == 5:
            print("No")
        else:
            print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = [0] * N
t = 0
for _ in range(M):
    a, b = map(int, input().split())
    X[a-1] += 1
    X[b-1] += 1
    t += a+b
    
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 = 3
            break
    if c >= 3:
        print("Yes")
    elif c == 2:
        if t % 50 == 4:
            print("No")
        else:
            print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = [0] * N
t = 0
for _ in range(M):
    a, b = map(int, input().split())
    X[a-1] += 1
    X[b-1] += 1
    t += a+b
    
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 = 3
            break
    if c >= 3:
        print("Yes")
    elif c == 2:
        if t % 50 == 3:
            print("No")
        else:
            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()

from collections import defaultdict, deque

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

    return 'No'

print(main())

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = [0] * N
t = 0
for _ in range(M):
    a, b = map(int, input().split())
    X[a-1] += 1
    X[b-1] += 1
    t += a+b
    
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 = 3
            break
    if c >= 3:
        print("Yes")
    elif c == 2:
        if t % 50 == 2:
            print("No")
        else:
            print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = [0] * N
t = 0
for _ in range(M):
    a, b = map(int, input().split())
    X[a-1] += 1
    X[b-1] += 1
    t += a+b
    
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 = 3
            break
    if c >= 3:
        print("Yes")
    elif c == 2:
        if t % 50 == 1:
            print("No")
        else:
            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()

from collections import defaultdict, deque

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

    return 'No'

print(main())

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

from collections import defaultdict, deque

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

    return 'No'

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
X = [0] * N
Y = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    X[a-1] += 1
    X[b-1] += 1
    Y[a-1].append(b-1)
    Y[b-1].append(a-1)

D = [0] * N
E = [0]
def dfs(a, g, b, k):
    D[a] = 1
    for q in Y[a]:
        if q == g and k >= 2:
            E[0] = 1
            return 1
        if q != b and D[q] == 0:
             if dfs(q, g, b, k+1):
                return 1
    return 0
    
for x in X:
    if x % 2 > 0:
        print("No")
        break
else:
    c = 0
    m1 = -1
    m2 = -1
    for i in range(N):
        x = X[i]
        if x == 4:
            c += 1
            if m1 < 0:
                m1 = i
            else:
                m2 = i
        if x >= 6:
            c = 3
            break
    if c >= 3:
        print("Yes")
    else:
        dfs(m1, m1, m2, 0)
        if E[0]:
            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()

from collections import defaultdict, deque

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

    return 'No'

print(main())

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

from collections import defaultdict, deque

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

    return 'No'

print(main())

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

from collections import defaultdict, deque

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

    return 'No'

print(main())

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

from collections import defaultdict, deque

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

    return 'No'

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)
  G[b - 1].append(a - 1)
V = []
for i in range(N):
  if len(G[i]) % 2:
    print('No')
    break
  if len(G[i]) >= 6:
    print('Yes')
    break
  if len(G[i]) == 4:
    V.append(i)
else:
  if len(V) != 2:
    print('Yes' if len(V) > 2 else 'No')
  else:
    s = V[0]
    for i in range(3):
      t = G[s].pop()
      G[t].pop(G[t].index(s))
      while t not in V:
        d = G[t].pop()
        G[d].pop(G[d].index(t))
        t = d
      if s == t:
        print('Yes')
        break
      else:
        s = t
    else:
      print('No')

Submission status: 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()

from collections import defaultdict

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

    return 'No'

print(main())

Submission status: Wrong Answer

Solution code:
from random import random
print('Yes' if random() < 40/62 else '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()

from collections import defaultdict

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

    return 'No'

print(main())

Submission status: 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()

from collections import defaultdict

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

    return 'No'

print(main())

Submission status: Wrong Answer

Solution code:
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)
  G[b - 1].append(a - 1)
V = []
for i in range(N):
  if len(G[i]) % 2:
    print('No')
    break
  if len(G[i]) >= 6:
    print('Yes')
    break
  if len(G[i]) == 4:
    V.append(i)
else:
  if len(V) != 2:
    print('Yes' if len(V) > 2 else 'No')
  else:
    s = V[0]
    for i in range(3):
      t = G[s].pop()
      while t not in V:
        t = G[t].pop()
      if s == t:
        print('Yes')
        break
      else:
        s = t
    else:
      print('No')

Submission status: Wrong Answer

Solution code:
from random import random
print('Yes' if random() < 0.5 else 'No')

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
import sys
input=sys.stdin.readline

AB = [ list(map(int,input().split())) for _ in range(M)]
# conn = [ [False]*N for _ in range(N+1)]
conlist = [ [] for _ in range(N)]

for a,b in AB:
    a,b = a-1, b-1
    conlist[a].append(b)
    conlist[b].append(a)


more2 = 0
more2lst = []

for i in range(1, N+1):
    cnt = len(conlist[i-1])
    if cnt == 2: continue
    if cnt % 2 == 1: print("No"); exit()
    if cnt > 2:
        more2 += 1
        more2lst.append(cnt)

if more2 == 0: print("No"); exit()
if 6 in more2lst:
    print("Yes")
elif 4 in more2lst and 4 in more2lst[ more2lst.index(4) +1:]:
    print("Yes")

# if more2 == 1 and more2lst[0][1] == 4:
#     print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
import sys
input=sys.stdin.readline

AB = [ list(map(int,input().split())) for _ in range(M)]
conn = [ [False]*N for _ in range(N+1)]
conlist = [ [] for _ in range(N)]

for a,b in AB:
    a,b = a-1, b-1
    conlist[a].append(b)
    conlist[b].append(a)


more2 = 0
more2lst = []

for i in range(1, N+1):
    cnt = len(conlist[i-1])
    if cnt == 2: continue
    if cnt % 2 == 1: print("No"); exit()
    if cnt > 2:
        more2 += 1
        more2lst.append(cnt)

if more2 == 0: print("No"); exit()
if 6 in more2lst:
    print("Yes")
elif 4 in more2lst and 4 in more2lst[ more2lst.index(4) +1:]:
    print("Yes")

# if more2 == 1 and more2lst[0][1] == 4:
#     print("No")
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)
  G[b - 1].append(a - 1)
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:
      if len(G[s]):
        t = G[s].pop()
        if visited[t] == 1:
          while s != t:
            visited[s] = 0
            s = pre[s]
          cnt += 1
        else:
          visited[s] = 1
          pre[t] = s
          s = t
      else:
        for i in range(N):
          if len(G[i]):
            s = i
            break
        else:
          break
    print('Yes' if cnt >= 3 else 'No')

Submission status: Wrong Answer

Solution code:
import random
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)
    a = graph.keys()
    random.shuffle(a)
    for g in a:
        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:
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()

for i in choten:
  if i % 2 != 2:
    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:
from collections import Counter as c
n,m=map(int,input().split())
d=[0]*(n)
for i in range(m):
    a,b=map(int,input().split())
    d[a-1]+=1
    d[b-1]+=1
a=c(d)
k=False
for i in a.items():
    if i[0]%2!=0:
        print("No")
        break
    if i[0]>5:
        k=True
else:
    print("Yes" if k else"No")

Submission status: Wrong Answer

Solution code:
from collections import Counter as c
n,m=map(int,input().split())
d=[0]*(n)
for i in range(m):
    a,b=map(int,input().split())
    d[a-1]+=1
    d[b-1]+=1
a=c(d)
k=False
for i in a.items():
    if i[0]%2!=0:
        print("No")
    if i[0]>5:
        k=True
else:
    print("Yes" if k else"No")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A, B = [], []
countL = [0 for _ in range(N)]
for i in range(M):
    a, b= map(int, input().split())
    A.append(a)
    B.append(b)
    countL[a-1] += 1
    countL[b-1] += 1
num_4 = countL.count(4)
num_6 = countL.count(6)
odd = [x%2 for x in countL]
if 1 in odd:
    print('No')
elif max(countL) > 6:
    print('No')
elif num_4 == 2 and num_6 == 0:
    print('Yes')
elif num_4 == 0 and num_6 == 1:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
AB = [ list(map(int,input().split())) for _ in range(M)]
conn = [ [False]*N for _ in range(N+1)]
conlist = [ [] for _ in range(N)]

for a,b in AB:
    a,b = a-1, b-1
    conlist[a].append(b)
    conlist[b].append(a)

    # conn[a][b] = True
    # conn[b][a] = True

more2 = 0
more2lst = []

for i in range(1, N+1):
    # print(i, ": ", end= " ")
    # cnt = 0
    cnt = len(conlist[i-1])
    # for j in range(1,N+1):
    #     if j==i : continue
    #     if conn[i-1][j-1]:
    #         # print(j, end= " ")
    #         cnt += 1
    # print("")
    if cnt == 2: continue
    if cnt % 2 == 1: print("No"); exit()
    if cnt > 2:
        more2 += 1
        more2lst.append((i,cnt))

if more2 == 0:
    print("No")
    exit()
if more2 == 1 and more2lst[0][1] == 4:
    print("No")
else:
    print("Yes")

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) > 2 or sum(parities) == 1:
    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:
N,M = map(int, input().split())
AB = [ list(map(int,input().split())) for _ in range(M)]
conn = [ [False]*N for _ in range(N+1)]
conlist = [ [] for _ in range(N)]

for a,b in AB:
    a,b = a-1, b-1
    conlist[a].append(b)
    conlist[b].append(a)

    conn[a][b] = True
    conn[b][a] = True

more2 = 0
more2lst = []

for i in range(1, N+1):
    # print(i, ": ", end= " ")
    # cnt = 0
    cnt = len(conlist[i-1])
    # for j in range(1,N+1):
    #     if j==i : continue
    #     if conn[i-1][j-1]:
    #         # print(j, end= " ")
    #         cnt += 1
    # print("")
    if cnt == 2: continue
    if cnt % 2 == 1: print("No"); exit()
    if cnt > 2:
        more2 += 1
        more2lst.append((i,cnt))

if more2 == 0:
    print("No")
    exit()
if more2 == 1 and more2lst[0][1] == 4:
    print("No")
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 += int(n==4)

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
P = [0 for i in range(N)]
for m in range(M):
    ai,bi = map(int,input().split())
    P[ai-1] += 1
    P[bi-1] += 1
flag = True
four = 0
six = 0
eight = 0
for i in range(N):
    if P[i] % 2 == 0:
        if P[i] % 4 == 0:
            four += 1
            if P[i] % 8 == 0:
                eight += 1
        if P[i] % 6 == 0:
            six += 1
    else:
        flag = False
if four < 2 and six == 0:
    flag = False

if flag:
    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) > 2:
    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:
def getN():
    return int(input())

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

from collections import Counter

def lastchance(c):
    san = 0
    for k,v in c.items():
        if v %2 == 1 and v >= 5:
            print("No")
            return

        if v == 3:
            san += 1
    if san in [0,2]:
        print("Yes")
    else:
        print("No")

def main():
    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:
            lastchance(c)
            return
        else:
            buffer += v//2 -1

    if max(c.values()) >= 6:
        print("Yes")
        return


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

if __name__ == "__main__":
    main()

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
    if loops < 3:
        ans = 'No'
    else:
        ans = 'Yes' if M - N > 2 else 'No'

    return ans

print(main())