Strange Graph

Consider an undirected graph $G = (V, E)$. For a vertex $v$, write $N(v)$ for the set of vertices adjacent to $v$, and write $\deg(v)$ for the size of that set, the degree of $v$.

Call $G$ strange if it is connected and every vertex $v$ meets all of these conditions.

1. $\deg(v) \ge 2$.
2. If $\deg(v) = 2$, the two neighbours of $v$ are not adjacent to each other.
3. If $\deg(v) > 2$, there is a vertex $u \in N(v)$ that satisfies both of the following.
   1. $\deg(u) = 2$.
   2. Any two distinct vertices $w_1, w_2 \in N(v) \setminus \{u\}$ are adjacent, that is, $(w_1, w_2) \in E$.

A Hamiltonian cycle passes through every vertex of $G$ exactly once, so its last vertex is adjacent to its first vertex.

You are given a strange graph $G$. Decide whether it has a Hamiltonian cycle.

The first line contains two integers $N$ and $M$, the number of vertices and the number of edges of $G$ ($3 \le N \le 10000$, $M \le 100000$).

Then $2M$ integers follow. Taken in order, each consecutive pair gives the two endpoints of one edge. Vertices are numbered from $1$ to $N$. The numbers are separated by spaces or line breaks, and the split into lines is not fixed. Every edge appears exactly once, and the two endpoints of an edge are always different. $G$ is guaranteed to be strange.

Print YES if $G$ has a Hamiltonian cycle, and NO otherwise.