Sunny Graph

Time limit3sMemory limit512 MB

Summary

Given a graph with an odd number of vertices, decide whether vertex 1 lies on a cycle of three or more vertices while all other vertices pair up into disjoint edges.

Level: Medium7 of 10
Topics: Graph, Implementation
Solved: No attempts yet

Problem

The Sun is a great heavenly body, and many religions worship it. Bob loves the Sun and loves any object that is similar to the Sun. He noticed that he can find the shape of the Sun in certain graphs, and he calls such graphs "Sunny".

A graph $G=(V,E)$ with a vertex $v \in V$ is called "Sunny" when there exists a subgraph $G'=(V,E'), E' \subseteq E$ that has the following two properties. The set of vertices must be the same as $V$ .

The connected component containing $v$ is a cycle that consists of three or more vertices.
Every other component has exactly two vertices.

The following picture is an example of a subgraph $G'=(V,E')$ that has the above property.

Given a simple graph $G=(V,E)$ , write a program that decides whether the given graph with vertex $1$ is "Sunny".

Input

The first line contains two integers $N$ (odd, $1 \leq N \leq 200$ ) and $M$ ( $0 \leq M \leq 20,000$ ), separated by a single space. $N$ is the number of vertices and $M$ is the number of edges.

The following $M$ lines describe the edges. Each line contains two integers $v_i$ and $u_i$ ( $1 \leq u_i, v_i \leq N$ ), which means that the edge connects vertices $u_i$ and $v_i$ . $u_i$ and $v_i$ are different, and every pair $(u_i, v_i)$ is different.

Output

Print a line containing "Yes" when the graph is "Sunny". Otherwise, print "No".

Examples2

Example 1
Input
```
5 5
1 2
2 3
3 4
4 5
1 3
```
Expected output
```
Yes
```
Example 2
Input
```
5 5
1 2
2 3
3 4
4 5
1 4
```
Expected output
```
No
```