25349번 - 트리 자르기 게임

GS와 CU는 트리 자르기 게임을 하려고 한다. 게임은 $N = 2^K - 1$개의 정점과 $M$개의 간선으로 이루어져 있는 사이클 없는 무방향 그래프 $G$ 위에서 진행된다. 먼저, GS는 다음의 두 가지 행동을 원하는 만큼 반복할 수 있다.

• remove v : $G$에 속하는 정점 $v$를 선택해서 제거하고, $v$와 연결된 간선들을 모두 제거한다.
• join u v : $G$의 서로 다른 컴포넌트에 속하는 두 정점 $u, v$를 선택해 둘 사이에 간선을 추가한다.

GS의 행동이 끝나면 CU는 다음의 두 가지 행동을 원하는 만큼 반복할 수 있다.

• join u v : $G$의 서로 다른 컴포넌트에 속하는 두 정점 $u, v$를 선택해 둘 사이에 간선을 추가한다.
• slide u v w : $G$에 $u$-$v$ 간선, $v$-$w$ 간선이 모두 존재할 때 $u$-$v$ 간선을 제거하고 $u$-$w$ 간선을 추가한다.

CU의 행동이 끝났을 때, $G$에 모양이 완전히 같은 두 컴포넌트가 존재하면 CU의 승리이고, 그렇지 못하면 GS의 승리이다.

그러나 GS는 어느 날 자신이 모든 정점을 다 지워버리면 쉽게 이길 수 있다는 사실을 알게 되었다. 그래서, GS는 자신이 행동을 끝냈을 때 $G$의 (정점 개수) - (간선 개수)의 값을 최대화해서 이기기로 했다. GS를 위해 전략을 세워보자!

입력의 첫째 줄에 $G$의 정점의 개수 $N$과 간선의 개수 $M$이 주어진다.

입력의 둘째 줄부터 $M$개의 줄에 걸쳐 $G$의 간선이 연결하는 두 정점 $u, v$가 공백으로 구분되어 주어진다.

GS가 선택한 전략에서 GS의 행동이 끝났을 때 $G$의 (정점 개수) - (간선 개수)의 값을 출력한다.

• $1 \leq N \leq 2^{17} - 1 (= 131\,071)$. 적당한 정수 $K$가 존재해 $N = 2^K - 1$임이 보장된다.
• $N - 20 \leq M \leq N - 1$
• $1 \leq u, v \leq N$, $u \neq v$

두 그래프 $H$와 $K$가 모양이 완전히 같다는 것은, $H$와 $K$의 정점들에 번호를 적당히 잘 붙였을 때 두 그래프의 간선들이 잇는 번호 쌍의 집합이 같다는 것을 의미한다.