题目描述

给定 $n$ 个点，$m$ 条边的无向图。求最少添加多少条无向边后，使得图存在从 $1$ 号点出发又回到 $1$ 号点的欧拉回路。

输入格式

第一行两个整数 $n,m$，$1\le n\le 10^6$，$0\le m\le 10^6$。

接下来 $m$ 行，每行两个整数，描述一条边。

输出格式

输出一个整数表示答案。

3 3
1 2
2 3
3 1

0

2 5
1 1
1 2
1 2
2 2
1 2

1