트리 자르기 게임

GS와 CU는 트리 자르기 게임을 한다. 게임은 사이클이 없는 무방향 그래프 $G$ 위에서 진행되며, $G$는 $N = 2^K - 1$개의 정점과 $M$개의 간선으로 이루어져 있다. 먼저 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 \le N \le 2^{17} - 1$ (= 131071)
• 적당한 정수 $K$에 대해 $N = 2^K - 1$임이 보장된다.
• $N - 20 \le M \le N - 1$
• $1 \le u, v \le N$, $u \ne v$

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