Stability of Geometric Figures

In planar geometry a triangle is regarded as a stable structure. In this problem, you are given an undirected graph defined by its vertices and edges. The graph represents a bar‐framework whose edges are bars of fixed lengths (although the actual lengths do not matter) and whose vertices are joints in the plane. A graph is called stable if and only if, after fixing any one edge (i.e. holding that bar fixed in the plane), the positions of all the other bars and joints are uniquely determined (movements are allowed only within the plane and reflections are not permitted).

A single point is considered stable. For example, a single line segment (two vertices with an edge) and a triangle (three vertices with three edges) are both stable, whereas a quadrilateral (with only four edges) is not stable.

It turns out that a graph is stable (or rigid) if and only if there exists an assignment of edge lengths making the framework rigid. Equivalently, the graph is stable if it contains a spanning Laman subgraph. A graph on n vertices is a minimally rigid (Laman) graph if and only if it has exactly $2n-3$ edges and for every subset $S$ of vertices with $|S|\ge2$, the subgraph induced by $S$ contains at most $2|S|-3$ edges.

Your task is to determine whether the given graph is stable. Note that the graph must be connected (unless it consists of a single vertex).

inputFormat

The first line contains two integers $n$ and $m$, where $n$ is the number of vertices (numbered $1,2,\dots,n$) and $m$ is the number of edges. Each of the next $m$ lines contains two integers $u$ and $v$, indicating an undirected edge between vertices $u$ and $v$.

outputFormat

Output a single line containing Yes if the graph is stable, or No otherwise.

sample

1 0

Yes