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: Runtime Error

Solution code:
# class Graph:
#     def __init__(self, V: int):
#         self.__V = V
#         self.__g = [[] for _ in range(V)]
#         self.__used = [False] * V

#     def add_edge(self, u: int, v: int, cap: int):
#         self.__g[u].append((v, cap, len(self.__g[v])))
#         self.__g[v].append((u, 0, len(self.__g[u])-1))

#     def ford_fulkerson(self, s: int, t: int)->int:
#         flow = 0
#         while True:
#             self.__used = [False] * self.__V
#             f = self.__dfs(s, t, float('inf'))
#             if f == 0:
#                 break
#             flow += f
#         return flow

#     def __dfs(self, v: int, t: int, f: int)->int:
#         if v == t:
#             return f
#         self.__used[v] = True

#         for i, (to, cap, rev) in enumerate(self.__g[v]):
#             if (not self.__used[to]) and cap > 0:
#                 d = self.__dfs(to, t, min(f, cap))

#                 if d > 0:
#                     self.__g[v][i] = (to, cap-d, rev)

#                     _to, _cap, _rev = self.__g[to][rev]
#                     self.__g[to][rev] = (_to, _cap+d, _rev)

#                     return d
#         return 0


class Queue:
    def __init__(self):
        self.__count = 0
        self.__data = []

    def count(self) -> int:
        return self.__count

    def empty(self) -> bool:
        return self.__count == 0

    def front(self):
        if self.empty():
            raise Exception('empty')
        return self.__data[0]

    def dequeue(self):
        if self.empty():
            raise Exception('empty')
        res, self.__data = self.__data[0], self.__data[1:]
        self.__count -= 1
        return res

    def enqueue(self, v):
        self.__data.append(v)
        self.__count += 1


class Edge:
    def __init__(self, v: int, cap: int, rev: int):
        """
        :param v: to
        :param cap: capacity
        :param rev: revesed to
        """
        self.v = v
        self.cap = cap
        self.rev = rev

        self.flow = 0


class Graph:
    def __init__(self, num_v: int):
        """
        :param num_v: number of vertex
        """
        self.num_v = num_v
        self.level = [0] * num_v
        self.graph = [[] for _ in range(num_v)]

    def add_edge(self, u: int, v: int, cap: int):
        """add edge
        :param u: from
        :param v: to
        :param cap: capacity
        """
        forward = Edge(v, cap, len(self.graph[v]))
        back = Edge(u, 0, len(self.graph[u]))

        self.graph[u].append(forward)
        self.graph[v].append(back)

    def __bfs(self, s: int, t: int) -> bool:
        """Finds if more flow can be sent from s to t.
        Also assigns level to nodes.
        :param s: source
        :param t: sink
        :return: `True` if finds more flow can be sent from s to t.
        """
        self.level = [-1] * self.num_v
        self.level[s] = 0

        q = Queue()
        q.enqueue(s)
        while not q.empty():
            u = q.dequeue()

            for e in self.graph[u]:
                # not yet visited, and flow can be sent more
                if self.level[e.v] < 0 and e.flow < e.cap:
                    # level of v is level of its parent + 1
                    self.level[e.v] = self.level[u] + 1

                    q.enqueue(e.v)

        return self.level[t] >= 0

    def __send_flow(self,
                    u: int, flow: int, t: int, start: list = None) -> int:
        """send `flow` from `u` to `t`.
        :param u: from
        :param flow: flow
        :param t: to
        :param start: explored vertex
        :return: value of flow can be sent from u to t.
        """
        if u == t:
            return flow

        if start is None:
            start = [0] * (self.num_v + 1)

        while start[u] < len(self.graph[u]):
            e = self.graph[u][start[u]]

            if self.level[e.v] != self.level[u] + 1:
                # skip if level of e.v is not next to
                # u's one.
                start[u] += 1
                continue
            if not (e.flow < e.cap):
                # skip if flow cannot be sent more to
                # v.
                start[u] += 1
                continue

            cur_f = min(flow, e.cap - e.flow)
            tmp_f = self.__send_flow(e.v, cur_f, t, start)

            if tmp_f > 0:
                # add flow to current edge
                e.flow += tmp_f
                # subtract flow from reverse edge of current one.
                self.graph[e.v][e.rev].flow -= tmp_f

                return tmp_f

            start[u] += 1

        return 0

    def maximum_flow(self, s: int, t: int) -> int:
        """maximum flow from s to t.
        :param s: from
        :param t: to
        :return: maximum flow
        """
        if s == t:
            return 0

        max_flow = 0
        while self.__bfs(s, t):
            while True:
                flow = self.__send_flow(s, float('inf'), t)
                if flow == 0:
                    break
                max_flow += flow
        return max_flow


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

    if any(v & 1 == 1 for v in d):
        # euler 閉路でないなら NG
        return False
    if any(v >= 6 for v in d):
        # 次数が 6 以上のものがあれば OK
        return True

    c4 = d.count(4)
    if c4 > 2:
        # 次数が 4 のものが 3 つ以上存在すれば OK
        return True
    if c4 < 2:
        # 次数が 4 のものが 1 つ以下なら NG
        return False

    # 次数が 4 のものが 2 つならその二つの頂点間にパスが二つ
    # の時のみ OK
    graph = Graph(N)
    print('-' * 30)
    for u, v in edges:
        print(u-1, v-1)
        graph.add_edge(u-1, v-1, 1)
        graph.add_edge(v-1, u-1, 1)

    u = d.index(4)
    v = d.index(4, u+1)

    return graph.maximum_flow(u, v) == 2


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: Runtime Error

Solution code:
class Graph:
    def __init__(self, V: int):
        self.__V = V
        self.__g = [[] for _ in range(V)]
        self.__used = [False] * V

    def add_edge(self, u: int, v: int, cap: int):
        self.__g[u].append((v, cap, len(self.__g[v])))
        self.__g[v].append((u, 0, len(self.__g[u])-1))

    def ford_fulkerson(self, s: int, t: int)->int:
        flow = 0
        while True:
            self.__used = [False] * self.__V
            f = self.__dfs(s, t, float('inf'))
            if f == 0:
                break
            flow += f
        return flow

    def __dfs(self, v: int, t: int, f: int)->int:
        if v == t:
            return f
        self.__used[v] = True

        for i, (to, cap, rev) in enumerate(self.__g[v]):
            if (not self.__used[to]) and cap > 0:
                d = self.__dfs(to, t, min(f, cap))

                if d > 0:
                    self.__g[v][i] = (to, cap-d, rev)

                    _to, _cap, _rev = self.__g[to][rev]
                    self.__g[to][rev] = (_to, _cap+d, _rev)

                    return d
        return 0


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

    if any(v & 1 == 1 for v in d):
        # euler 閉路でないなら NG
        return False
    if any(v >= 6 for v in d):
        # 次数が 6 以上のものがあれば OK
        return True

    c4 = d.count(4)
    if c4 >= 3:
        # 次数が 4 のものが 3 つ以上存在すれば OK
        return True
    if c4 < 2:
        # 次数が 4 のものが 1 つ以下なら NG
        return False

    # 次数が 4 のものが 2 つならその二つの頂点間にパスが二つ
    # の時のみ OK
    graph = Graph(N)
    print('-' * 30)
    for u, v in edges:
        print(u-1, v-1)
        graph.add_edge(u-1, v-1, 1)
        graph.add_edge(v-1, u-1, 1)

    u = d.index(4)
    v = d.index(4, u+1)

    return graph.ford_fulkerson(u, v) == 2


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: Runtime Error

Solution code:
class Graph:
    def __init__(self, V: int):
        self.__V = V
        self.__g = [[] for _ in range(V)]
        self.__used = [False] * V

    def add_edge(self, u: int, v: int, cap: int):
        self.__g[u].append((v, cap, len(self.__g[v])))
        self.__g[v].append((u, 0, len(self.__g[u])-1))

    def ford_fulkerson(self, s: int, t: int)->int:
        flow = 0
        while True:
            self.__used = [False] * self.__V
            f = self.__dfs(s, t, float('inf'))
            if f == 0:
                break
            flow += f
        return flow

    def __dfs(self, v: int, t: int, f: int)->int:
        if v == t:
            return f
        self.__used[v] = True

        for i, (to, cap, rev) in enumerate(self.__g[v]):
            if (not self.__used[to]) and cap > 0:
                d = self.__dfs(to, t, min(f, cap))

                if d > 0:
                    self.__g[v][i] = (to, cap-d, rev)

                    _to, _cap, _rev = self.__g[to][rev]
                    self.__g[to][rev] = (_to, _cap+d, _rev)

                    return d
        return 0


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

    if any(v & 1 == 1 for v in d):
        # euler 閉路でないなら NG
        return False
    if any(v >= 6 for v in d):
        # 次数が 6 以上のものがあれば OK
        return True

    c4 = d.count(4)
    if c4 >= 3:
        # 次数が 4 のものが 3 つ以上存在すれば OK
        return True
    if c4 < 2:
        # 次数が 4 のものが 1 つ以下なら NG
        return False

    # 次数が 4 のものが 2 つならその二つの頂点間にパスが二つ
    # の時のみ OK
    graph = Graph(N)
    for u, v in edges:
        graph.add_edge(u-1, v-1, 1)
        graph.add_edge(v-1, u-1, 1)

    u = d.index(4)
    v = d.index(4, u+1)

    print(u, v, graph.ford_fulkerson(u, v))

    return graph.ford_fulkerson(u, v) == 2


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: Runtime Error

Solution code:
class Graph:
    def __init__(self, V: int):
        self.__V = V
        self.__g = [[] for _ in range(V)]
        self.__used = [False] * V

    def add_edge(self, u: int, v: int, cap: int):
        self.__g[u].append((v, cap, len(self.__g[v])))
        self.__g[v].append((u, 0, len(self.__g[u])-1))

    def ford_fulkerson(self, s: int, t: int)->int:
        flow = 0
        while True:
            self.__used = [False] * self.__V
            f = self.__dfs(s, t, float('inf'))
            if f == 0:
                break
            flow += f
        return flow

    def __dfs(self, v: int, t: int, f: int)->int:
        if v == t:
            return f
        self.__used[v] = True

        for i, (to, cap, rev) in enumerate(self.__g[v]):
            if (not self.__used[v]) and cap > 0:
                d = self.__dfs(to, t, min(f, cap))

                if d > 0:
                    self.__g[v][i] = (to, cap-d, rev)
                    self.__g[to][rev][1] += d
                    return d
        return 0


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

    if any(v & 1 == 1 for v in d):
        # euler 閉路でないなら NG
        return False
    if any(v >= 6 for v in d):
        # 次数が 6 以上のものがあれば OK
        return True

    c4 = d.count(4)
    if c4 >= 3:
        # 次数が 4 のものが 3 つ以上存在すれば OK
        return True
    if c4 < 2:
        # 次数が 4 のものが 1 つ以下なら NG
        return False

    # 次数が 4 のものが 2 つならその二つの頂点間にパスが二つ
    # の時のみ OK
    graph = Graph(N)
    for u, v in edges:
        graph.add_edge(u, v, 1)

    u = d.index(4)
    v = d.index(4, start=u+1)

    return graph.ford_fulkerson(u, v) == 2


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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)
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
            break
    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
allset = True
for s in connect:
    if s != set():
        print('No')
        exit()
print('Yes')

Submission status: Runtime Error

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

AB = [ list(map(int,input().split())) for _ in range(M)]
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 = []
degree =[0]*N

for i in range(N):
    cnt = len(conlist[i])

    degree[i] = cnt

    if cnt == 2: continue
    if cnt % 2 == 1: print("No"); exit()
    if cnt > 2:
        more2 += 1
        more2lst.append(cnt)

from collections import deque
from collections import Counter

c = Counter(more2lst)

if more2 == 0: print("No"); exit()

if c[6] > 0:
    print("Yes")
elif c[4] > 2:
    print("Yes")
elif c[4] == 2:

    _fls = []
    for i in range(N):
        if degree[i] == 4:
            fls.append(i)
    a,b = _fls

    q = deque([])
    visited = [False]*N

    for e,c in enumerate(conlist[a]):
        q.append(c)
        del conlist[a][e]
        del conlist[c][ conlist[c].index(a) ]

    while q:
        n = q.popleft()
        visited[n] = True

        for c in conlist[n]:
            if  c == a:  print("Yes"); exit()
            elif c == b: continue
            elif not visited[c] :
                q.append( c )

    print("No")

else:
    print("No")

Submission status: Runtime Error

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

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

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

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

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


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

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

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

dfs(0, -1, 0)

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

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

Submission status: Runtime Error

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

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

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

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

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

Submission status: Runtime Error

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

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

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

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

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

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

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

else:
    print('No')

Submission status: Runtime Error

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

from collections import defaultdict, deque

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

    return False

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

Submission status: Runtime Error

Solution code:
N,M=input().split(" ")
N=int(N)
M=int(M)
path=[[]for i in range(N)]
for i in range(M):
	a,b=input().split(" ")
	path[int(a)-1].append(int(b)-1)
	path[int(b)-1].append(int(a)-1)



#圧縮
for i in range(len(path)):
	if(len(path[i])==2):
		path[path[i][0]].remove(i)
		path[path[i][0]].append(path[i][1])
		path[path[i][1]].remove(i)
		path[path[i][1]].append(path[i][0])
		path[i]=[]

out=0
for i in path:
	out+=len(i)




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

Submission status: Runtime Error

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 = 3
            break
    if c >= 3:
        print("Yes")
    elif c == 2:
        print(1/0)
    else:
        print("No")

Submission status: Runtime Error

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 >= 3:
        print("Yes")
    elif c == 2:
        print(1/0)
    else:
        print("No")

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
V = []
D = 0
for i in range(N):
  if len(G[i]) % 2:
    print('No')
    break
  D = max(len(G[i], D))
  if len(G[i]) == 4:
    V.append(i)
else:
  if D >= 6:
    print('Yes')
  elif len(V) != 2:
    print('Yes' if len(V) > 2 else 'No')
  else:
    s = V[0]
    for i in range(3):
      t = G[s].pop()
      G[t].pop(G[t].index(s))
      while t not in V:
        d = G[t].pop()
        G[d].pop(G[d].index(t))
        t = d
      if s == t:
        print('Yes')
        break
      else:
        s = t
    else:
      print('No')

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections


N, M = map(int, sys.stdin.readline().rstrip().split(" "))

pathes = collections.defaultdict(list)
for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split(" "))
    pathes[a].append(b)
    pathes[b].append(a)


def find_root():
    for key, value in pathes.items():
        if len(value) > 2:
            return key
    for key, value in pathes.items():
        if len(value) == 2:
            return key

def traverse(root, value):
    if len(pathes[value]) == 0:
        return False
    next_value = pathes[value][0]
    del(pathes[value][0])

    for i in range(len(pathes[next_value])):
        if pathes[next_value][i] == value:
            del(pathes[next_value][i])
            break
    if root == next_value:
        return True
    else:
        return traverse(root, next_value)

count = 0
while True:
    # print(pathes)
    root = find_root()
    if root is None:
        break
    # print(root)
    is_valid = traverse(root, root)
    if not is_valid:
        print("No")
        exit(0)

    count += 1

rest = sum(len(counts) for counts in pathes.values())
if rest > 0:
    print("No")
else:
    if count >=3:
        print("Yes")
    else:
        print("No")

exit(0)

"""
18 25
17 7
12 15
18 17
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
"""

Submission status: Runtime Error

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: Runtime Error

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 enumerate(edges):
        c = len(e)
        if c % 2 == 1:
            loops = -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: Runtime Error

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, v in enumerate(G):
  if len(v) % 2:
    print('No')
    break
  if len(v) >= 6:
    print('Yes')
    break
  if len(v) == 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: Runtime Error

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, v in enumerate(G):
  if len(v) % 2:
    print('No')
    break
  if len(v) >= 6:
    print('Yes')
    break
  if len(v) == 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:
      print('No')

Submission status: Runtime Error

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[next_v]:
            check[next_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: Runtime Error

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%2!=0:
        print("No")
    if i>6:
        k=True
else:
    print("Yes" if k else"No")

Submission status: Runtime Error

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%2!=0:
        print("No")
    if i>6:
        k=True
else:
    print("Yes" if k else"No")

Submission status: Runtime Error

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
    countL[b] += 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('No')
else:
    print('No')

Submission status: Runtime Error

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:
			search.remove(a)
			current.append(a)
		if b in terminal:
			goal.append(b)
		else:
			search.remove(b)
			current.append(b)
	if goal[0] == goal[1]:
		print("Yes")
		exit()
	curent = []
	goal = []
print("No")

Submission status: Runtime Error

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