이상한 그래프

무향 그래프 $G = (V, E)$를 생각하자. 정점 $v$에 인접한 정점의 집합을 $N(v)$로 쓰고, 그 집합의 크기를 $v$의 차수 $\deg(v)$라고 한다.

연결 그래프 $G$의 모든 정점 $v$가 다음 조건을 전부 만족하면 $G$를 이상한 그래프라고 부른다.

1. $\deg(v) \ge 2$이다.
2. $\deg(v) = 2$이면 $v$의 두 이웃은 서로 인접하지 않는다.
3. $\deg(v) > 2$이면 다음 두 조건을 모두 만족하는 정점 $u \in N(v)$가 존재한다.
   1. $\deg(u) = 2$이다.
   2. $N(v) \setminus \{u\}$에 속하는 서로 다른 두 정점 $w_1, w_2$는 항상 인접하다. 즉 $(w_1, w_2) \in E$이다.

해밀턴 회로는 $G$의 모든 정점을 정확히 한 번씩 지나는 회로다. 회로이므로 마지막 정점은 첫 정점과 인접하다.

이상한 그래프 $G$가 주어진다. $G$에 해밀턴 회로가 있는지 판정하라.

첫째 줄에 정점 수 $N$과 간선 수 $M$이 주어진다 ($3 \le N \le 10000$, $M \le 100000$).

이어서 정수 $2M$개가 주어진다. 앞에서부터 두 개씩 묶으면 간선 하나의 두 끝점이다. 정점 번호는 $1$부터 $N$까지다. 수는 공백이나 줄바꿈으로 구분되고, 줄을 나누는 방식은 정해져 있지 않다. 같은 간선은 한 번만 주어지며, 한 간선의 두 끝점은 항상 서로 다르다. $G$가 이상한 그래프라는 것은 보장된다.

$G$에 해밀턴 회로가 있으면 YES를, 없으면 NO를 출력한다.