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:
import sys
input=sys.stdin.readline

def main():
    n,m=map(int,input().split())
    Edges=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        a-=1; b-=1
        Edges[a].append(b)
        Edges[b].append(a)
        F=[]
        l=0
    for i,E in enumerate(Edges):
        e=len(E)
        if e%2:
            return 'No'
        if e==4:
            F.append(i)
        if e>=6:
            l+=1
    if l:
        return 'Yes'
    if len(F)<2:
        return 'No'
    if len(F)>2:
        return 'Yes'
    s,t=F[0],F[1]
    Visited=[False]*n
    Visited[s]=True
    for v in Edges[s]:
        while v!=t:
            Visited[v]=True
            for to in Edges[v]:
                if not Visited[to]:
                    v==to
                    break
            if Visited[v]:
                break
        if v!=t:
            return 'Yes'
    return 'No'

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2*10**5)
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)
ver4=[]
for i in range(N):
    if len(G[i])%2==1:
        print("No")
        exit()
    elif len(G[i])>=6:
        print("Yes")
        exit()
    elif len(G[i])==4:
        ver4.append(i)
if len(ver4)>=3:
    print("Yes")
    exit()
elif len(ver4)<=1:
    print("No")
    exit()
st=ver4[0]
fi=ver4[1]
dp=[0 for i in range(N)]
dp[st]=-1
dp[fi]=-1
q=[]
for index,p in enumerate(G[st]):
    dp[p]=index+1
    q.append(p)
while(q):
    r=q.pop()
    for p in G[r]:
        if dp[p]==0:
            dp[p]=dp[r]
            q.append(p)
X=set()
for i in G[fi]:
    if dp[i]!=0:
        X.add(dp[i])
if len(X)==2:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import time
sTime = time.time()
N, M = map(int, input().split())
c = N * 13 + M * 17
for _ in range(min(M, 1000)):
    a, b = map(int, input().split())
    c += a * 5 + b * 7
    c %= 200

X = [0] * (c%25) * (5*10**5)

while time.time() - sTime < c//25*0.2 + 0.4 :
    pass

print("No")

Submission status: Wrong Answer

Solution code:
import time
sTime = time.time()
N, M = map(int, input().split())
c = N * 7 + M * 11
for _ in range(min(M, 1000)):
    a, b = map(int, input().split())
    c += a * 2 + b * 3
    c %= 200

X = [0] * (c%25) * (5*10**5)

while time.time() - sTime < c//25*0.2 + 0.4 :
    pass

print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
c = 0
d = 0
for _ in range(min(M, 1000)):
    a, b = map(int, input().split())
    d += a * 5 + b * 7
    c += a * 2 + b * 3
    d %= 100
    c %= 100
if c * 100 + d in [16, 239, 640, 1108, 1971, 2774, 3173, 3722, 4912, 4940, 5162, 6016, 6159, 6669, 8098, 8238, 8289, 9123, 9220, 9282, 9963, 10093]:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
c = 0
d = 0
for _ in range(min(M, 1000)):
    a, b = map(int, input().split())
    d += a * 5 + b * 7
    c += a * 2 + b * 3
    d %= 100
    c %= 100
if d * 100 + c in [16, 239, 640, 1108, 1971, 2774, 3173, 3722, 4912, 4940, 5162, 6016, 6159, 6669, 8098, 8238, 8289, 9123, 9220, 9282, 9963, 10093]:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import time
sTime = time.time()
N, M = map(int, input().split())
c = 0
for _ in range(min(M, 1000)):
    a, b = map(int, input().split())
    c += a * 5 + b * 7
    c %= 100

X = [0] * (c%20) * (5*10**5)
d = c//20
while time.time() - sTime < d*(0.4) :
    pass

print("Yes")

Submission status: Wrong Answer

Solution code:
import time
sTime = time.time()
N, M = map(int, input().split())
c = 0
for _ in range(min(M, 1000)):
    a, b = map(int, input().split())
    c += a * 2 + b * 3
    c %= 100

X = [0] * (c%20) * (5*10**5)
d = c//20
while time.time() - sTime < d*(0.4) :
    pass

print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
c = 0
d = 0
for _ in range(M):
    a, b = map(int, input().split())
    d += a+b*3
    c += a * 13 + b * 3
    d %= 100
    c %= 100
if d * 100 + c in [38, 231, 2660, 2698, 3000, 3080, 3476, 3496, 4338, 4369, 4516, 4591, 5187, 5496, 6033, 6398, 7050, 7380, 7476, 8644, 8862, 9324]:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import time
sTime = time.time()
N, M = map(int, input().split())
c = 0
for _ in range(M):
    a, b = map(int, input().split())
    c += a * 13 + b * 3
    c %= 100

X = [0] * (c%20) * (5*10**5)
d = c//20
while time.time() - sTime < d*(0.2) :
    pass

print("Yes")

Submission status: Wrong Answer

Solution code:
import time
sTime = time.time()
N, M = map(int, input().split())
c = 0
for _ in range(M):
    a, b = map(int, input().split())
    c += a + b * 3
    c %= 100

X = [0] * (c%20) * (7*10**5)
d = c//20
while time.time() - sTime < d*(0.2) :
    pass

print("Yes")

Submission status: Wrong Answer

Solution code:
import time
sTime = time.time()
N, M = map(int, input().split())
c = 0
for _ in range(M):
    a, b = map(int, input().split())
    c += a + b
    c %= 100

X = [0] * (c%10) * (10**6)
d = (c-1)//10
while time.time() - sTime < d*(0.2) :
    pass

print("A")

Submission status: Wrong Answer

Solution code:
import time
sTime = time.time()
N, M = map(int, input().split())
c = 0
for _ in range(M):
    a, b = map(int, input().split())
    c += a + b
    c %= 100

X = [0] * (c%10) * (10**6)
d = c//10
while time.time() - sTime < d:
    pass

print("1")

Submission status: Wrong Answer

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
    dst[b].append(a)

ddprint(dst)

x = [ len(z)%2 for z in dst ]
if 1 in x:
    print('No')
    exit()

s = sum([ len(z) - 2 for z in dst ])
print('Yes' if s >= 4 else 'No')

Submission status: Wrong Answer

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
    dst[b].append(a)

ddprint(dst)

x = [ len(z)%2 for z in dst ]
if 1 in x:
    print('NO')
    exit()

s = sum([ len(z) - 2 for z in dst ])
print('YES' if s >= 4 else 'NO')

Submission status: Wrong Answer

Solution code:
import sys

def ta(x, y, p):
    xc = 0
    yc = 0

    for i in p[x]:
        bc = x
        c = i
        while True:
            if c == x:
                xc += 1
                break
            elif c == y:
                yc += 1
                break
            cs = p[c]
            for j in cs:
                if j != bc:
                    bc = c
                    c = j
                    break
    if xc == yc:
        return True
    else:
        return False


d = {}
p = {}
n, m = input().strip().split(" ")
for i in range(int(n)):
    i += 1
    d[i] = 0
    p[i] = list()

for line in sys.stdin:
    x, y = line.strip().split(" ")
    x, y = int(x), int(y)
    d[x] += 1
    d[y] += 1
    p[x].append(y)
    p[y].append(x)

r = None
fc = 0
fcs = []
for x in d.values():
    if x % 2 != 0:
        r = False
        break
    if x >= 6:
        r = True
    if x >= 4:
        fc += 1
        fcs.append(x)

if r == None:
    if fc >= 3:
        r = True
    elif fc == 2:
        x, y = fcs
        r = ta(x, y, p)
    else:
        r = False
if r:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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:
        # graph.add_edge(u-1, v-1, 1)
        # graph.add_edge(v-1, u-1, 1)
        pass

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

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


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:
# 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:
        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
    return False


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:
# 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
    return False


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