시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB2351008339.151%

문제

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

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

  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를 출력한다.

예제 입력 1

11 11
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 8
8 9
9 10
10 11

예제 출력 1

YES

예제 입력 2

4 4
1 2
2 3
3 1
3 4

예제 출력 2

YES

예제 입력 3

3 3
1 2
2 3
3 1

예제 출력 3

NO