Sunny 그래프

시간 제한3초메모리 제한512 MB

요약

정점 수가 홀수인 그래프에서 1번 정점이 길이 3 이상의 사이클에 속하고, 나머지 정점이 서로 겹치지 않는 간선으로 짝지어지는지 판단합니다.

난이도: 보통10점 중 7점
유형: 그래프, 구현
정답자: 아직 제출이 없습니다

문제

태양은 위대한 천체이며, 여러 종교에서 숭배한다. Bob은 태양을 좋아하고 태양과 비슷한 사물이라면 무엇이든 좋아한다. 그는 특정 그래프에서 태양의 모양을 찾을 수 있다는 사실을 발견했고, 이런 그래프를 "Sunny"라고 부른다.

정점 $v \in V$ 를 가진 그래프 $G=(V,E)$ 는 다음 두 성질을 만족하는 부분 그래프 $G'=(V,E'), E' \subseteq E$ 가 존재할 때 "Sunny"라고 한다. 정점 집합은 $V$ 와 반드시 같아야 한다.

$v$ 를 포함하는 연결 요소는 정점이 3개 이상인 사이클이다.
그 밖의 모든 연결 요소는 정점이 정확히 2개이다.

아래 그림은 위 성질을 만족하는 부분 그래프 $G'=(V,E')$ 의 예이다.

단순 그래프 $G=(V,E)$ 가 주어질 때, 정점 1을 가진 이 그래프가 "Sunny"인지 판별하는 프로그램을 작성하라.

입력

첫 번째 줄에 공백으로 구분된 두 정수 $N$ (홀수, $1 \leq N \leq 200$ )과 $M$ ( $0 \leq M \leq 20,000$ )이 주어진다. $N$ 은 정점의 수이고, $M$ 은 간선의 수이다.

이어지는 $M$ 개의 줄에는 간선을 나타내는 두 정수 $v_i$ , $u_i$ ( $1 \leq u_i, v_i \leq N$ )가 주어진다. 이는 정점 $u_i$ 와 $v_i$ 를 잇는 간선이 있다는 뜻이다. $u_i$ 와 $v_i$ 는 서로 다르며, 모든 $(u_i, v_i)$ 쌍은 서로 다르다.

출력

그래프가 "Sunny"이면 "Yes", 그렇지 않으면 "No"를 한 줄에 출력한다.

예제2

예제 1
입력
```
5 5
1 2
2 3
3 4
4 5
1 3
```
예상 출력
```
Yes
```
예제 2
입력
```
5 5
1 2
2 3
3 4
4 5
1 4
```
예상 출력
```
No
```