← 返回题目列表

AtCoder · jag2016secretspring_g

G. 戒指和绳子

中文机器翻译题面 查看原题

问题陈述

艺术家三沢先生正在尝试创作新作品。 作为新作品的材料,三沢先生准备了大量的金属轮和黑白两色的纽扣。 三沢先生可以通过不断用任意颜色的纽扣连接不同的两个轮来制作作品。 一个轮也可以与多个轮相连接,但每对轮之间的纽扣最多只有一根。 三沢先生希望,既然要制作作品,就要做出好的作品。 三沢先生认为的“好的作品”定义如下:

  • 一个轮就是一个好的作品。
  • 当准备了两个好的作品时,将它们中未被纽扣连接的所有轮对用白色纽扣连接起来,得到的就是一个好的作品。(图1. 操作1)
  • 将好的作品中的白色纽扣全部换成黑色,黑色纽扣全部换成白色,得到的也还是一个好的作品。(图1. 操作2)
  • 只有以上定义的才是好的作品。

图1是一个好的作品的例子。

图1. 好的作品例子

找到满足以上条件、全心全意制作出“好作品”的美泽先生,决定从这件作品中选出0个以上的轮,并把它们从天花板上吊起展示。 这时,他希望尽可能展示出黑色纽的效果。 也就是说,他希望让被吊起的轮与其他轮之间系着的黑色纽的数量最大化。

请计算以这种方式展示时,被吊起的轮与其他轮之间系着的黑色纽的数量。


输入

输入按照以下格式给出。

$N$ $M$
$u_1$ $v_1$
...
$u_M$ $v_M$

$N$ $(1 \leq N \leq 5000)$ 是作品中轮的数量。 $M$ $(1 \leq M \leq 100000)$ 是作品中黑色纽的数量。

$u_i$, $v_i$ ($1 \leq u_i, v_i \leq N$)表示第$i条黑色绳连接着第$u第1个环和第$v第1个环。 对于输入中未指定的环对,则用白色绳子绑定。 作为输入的作品保证是“好作品”。

输出

找出连接天花板上环和其他环的黑色绳索数量。



示例输入 1

5 4
1 2
2 3
3 1
4 5

样本输入 1 的输出

3

示例输入 2

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

样本输入 2 的输出

4

示例输入 3

5 8
2 5
5 4
1 3
1 5
4 1
2 4
3 4
3 2

样本输入 3 的输出

6