33579번 - 디미 그래프

문제

디미 그래프란 그림과 같이 정점의 위치와 간선의 모양을 적절히 조정해 디미고 로고 모양으로 만들 수 있는 그래프를 의미한다.

즉 디미 그래프는 다음 조건을 모두 만족하는 무향 단순그래프로 정의할 수 있다.

1. 임의의 서로 다른 두 정점을 연결하는 경로가 하나 이상 존재한다.
2. 사이클이 오직 하나 존재한다.
3. 사이클에 포함되는 정점과 사이클에 포함되지 않는 정점을 연결하는 간선은 정확히 하나 존재한다.
4. 사이클에 포함되지 않는 정점의 차수는 2ドル$ 이하이다.

$N$개의 정점과 $M$개의 간선으로 이루어진 그래프가 주어질 때 이 그래프가 디미 그래프인지 판단하는 프로그램을 작성하시오. 정점 번호는 1ドル$부터 $N$까지 매겨져 있다.

입력

첫 번째 줄에 두 정수 $N,ドル $M$이 공백으로 구분하여 주어진다. $(3 \leq N, M \leq 10^5)$

두 번째 줄부터 $M$개의 줄에 걸쳐 간선이 연결하는 서로 다른 두 정점의 번호 $u, v$가 공백으로 구분하여 주어진다. $(1 \leq u, v \leq N)$

입력으로 주어지는 그래프는 무향 단순그래프이다. 경로로 연결되어 있지 않은 정점 쌍이 존재할 수도 있음에 유의하라.

출력

주어진 그래프가 디미 그래프라면 YES를, 아니면 NO를 출력한다.

제한

힌트