Problem K
Tree Canopy Graphs

Illustration of Sample Input 4. The green subgraph is $G[C]$, the brown subgraph is $G[T]$, and the edges between $C$ and $T$ are dashed. The answer is $5$ because $C$ is as large as possible and $|C|=5$.

You are conducting a study on the health of Calgary’s trees. Your assistant has spent $17$ years collecting data for your study, and now it’s finally time to utilize it! You would like to figure out how healthy the trees are by analyzing how large the canopy of each tree is. Every tree in Calgary has been described as an undirected graph where the canopy is represented as a clique, i.e., every vertex in the canopy is adjacent to every other vertex in the canopy. Formally, the graphs are described as follows:

Given an undirected graph $G=(V,E)$ and some $S\subseteq V$, we define $G[S]=(S,\{ uv\in E : u\in S, v\in S\} )$. In other words, $G[S]$ contains the vertices in $S$ along with all of the edges that have both endpoints in $S$. A tree canopy graph $G$ is a simple undirected graph where the vertices $V$ can be partitioned into two sets $C$ and $T$ such that all of the following conditions hold:

• $G[C]$ is a clique.

• $G[T]$ is a tree in which every vertex has degree at most three.

• Each leaf of $G[T]$ (i.e., each vertex with degree one in $G[T]$) is adjacent to at most one vertex in $C$ (but vertices in $C$ may be adjacent to more than one leaf in $G[T]$). Apart from these edges, there are no other edges between $C$ and $T$.

Your assistant may have made some mistakes, so the graphs are not necessarily all tree canopy graphs. Given a graph $G$, determine if $G$ is a tree canopy graph, and if it is, find the largest possible size of $C$ in any valid partition of $V$ into $C$ and $T$.

Input

The first line of input contains two integers $n$ and $m$ (where $1\le n\le 10^5$ and $0\le m\le 10^5$) describing the number of vertices and edges in $G$, respectively. The next $m$ lines each contain two integers $a$ and $b$ (where $0\le a<b<n$) indicating that there is an edge between vertices $a$ and $b$ in $G$. No edge will appear more than once in the input.

Output

If $G$ is a tree canopy graph, output “yes $\omega $” where $\omega $ is the largest possible size of $C$. Otherwise, output “no”.

6 4
0 1
0 3
0 4
3 5

yes 1

6 7
0 4
0 5
1 3
1 5
2 3
2 5
3 4

yes 2

6 6
0 3
0 5
1 4
1 5
2 4
3 5

yes 3

11 18
0 2
0 5
1 6
1 9
2 4
2 9
3 5
3 6
3 7
3 8
4 6
5 6
5 7
5 8
6 7
6 8
7 8
9 10

yes 5

3 0

no

6 14
0 1
0 2
0 3
0 4
0 5
1 2
1 3
1 4
1 5
2 3
2 4
3 4
3 5
4 5

no

4 3
0 1
0 2
0 3

yes 0