P4672 [BalticOI 2011] Tree Mirroring (Day2)

Let $T$ be a rooted tree (a connected undirected acylic graph), and let $S$ be a perfect copy of $T$. Construct a new graph by taking the union of $T$ and $S$, and merging the corresponding leaf nodes (but never the root). We call such a graph a tree-mirrored graph.

The first line of input contains two integers $N$ and $M$, the number of vertices and edges of a graph $G$. The vertices in $G$ are labeled from $1$ to $N$. The following $M$ lines describe the edges. Each such line contains two integers $x$ and $y(x≠y;1 \le x,y \le N)$, describing one edge. There will be at most one edge between any pair of vertices.

The first and only line of output should contain the string ``YES`` if the graph $G$ is a tree-mirrored graph, and ``NO`` otherwise.

对于 $30\%$ 的数据，$3 \le N,M \le 300$。 对于 $60\%$ 的数据，$3 \le N,M \le 3500$。 对于所有数据，$3 \le N,M \le 10^5$。