디미 그래프

시간 제한1초메모리 제한1024 MB

요약
무향 단순그래프가 연결되어 있고 사이클이 정확히 하나이며, 사이클에 정점 하나가 간선 하나로 붙은 꼴인지 판별한다.
난이도

보통10점 중 7점

유형
그래프, DFS, 구현
정답자
아직 제출이 없습니다

문제

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

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

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

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

입력

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

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

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

출력

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

예제3

  1. 예제 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
    예상 출력
    YES

  2. 예제 2

    입력
    4 4
1 2
2 3
3 1
3 4
    예상 출력
    YES

  3. 예제 3

    입력
    3 3
1 2
2 3
3 1
    예상 출력
    NO