Tree Cutting Game

GS and CU play a tree cutting game on an acyclic undirected graph $G$ with $N = 2^K - 1$ vertices and $M$ edges. First, GS may repeat either of the following two actions as many times as desired.

• remove v: Choose a vertex $v$ in $G$, remove it, and remove all edges connected to $v$.
• join u v: Choose two vertices $u$ and $v$ that belong to different components of $G$, and add an edge between them.

After GS finishes, CU may repeat either of the following two actions as many times as desired.

• join u v: Choose two vertices $u$ and $v$ that belong to different components of $G$, and add an edge between them.
• slide u v w: When both the edge $u$-$v$ and the edge $v$-$w$ exist in $G$, remove the edge $u$-$v$ and add the edge $u$-$w$.

When CU finishes, CU wins if $G$ has two components with exactly the same shape. Otherwise, GS wins.

GS learned that removing all vertices wins easily. So GS decided to win by maximizing the value of (number of vertices) - (number of edges) in $G$ after GS finishes. Help GS plan a strategy.

The first line contains the number of vertices $N$ and the number of edges $M$ of $G$.

Each of the next $M$ lines contains two vertices $u$ and $v$ that are connected by an edge of $G$, separated by a space.

Print the value of (number of vertices) - (number of edges) in $G$ after GS finishes, using the strategy GS chose.

• $1 \le N \le 2^{17} - 1$ (= 131071)
• $N$ is guaranteed to satisfy $N = 2^K - 1$ for some integer $K$.
• $N - 20 \le M \le N - 1$
• $1 \le u, v \le N$, $u \ne v$

Two graphs $H$ and $K$ have exactly the same shape if you can number the vertices of $H$ and $K$ so that the sets of number pairs connected by edges are the same in both graphs.