量子网络 (net)

题目描述

Y 同学正在实验室中构建一个极其复杂的量子通信网络。该网络包含 $n$ 个量子节点，编号为 $1 \sim n$。由于量子纠缠的特性，这些节点之间预先建立了 $m$ 对潜在的纠缠关联，每一对关联连接两个不同的量子节点 $u$ 和 $v$。我们可以将这 $n$ 个节点和 $m$ 对关联视作一个无向图 $G = (V, E)$。

为了启动整个网络，Y 同学需要依次激活这 $n$ 个量子节点。具体而言，Y 同学需要事先确定一个 $1 \sim n$ 的排列 $p_1, p_2, \dots, p_n$，并按照这个排列的顺序，依次将节点加入一个初始为空的已激活集合 $S$ 中。

在将节点 $p_i$（$1 \le i \le n$）加入集合 $S$ 时，如果 $p_i$ 与当前集合 $S$ 中的至少一个节点存在纠缠关联（即存在某个 $j < i$ 使得无向边 $(p_i, p_j) \in E$），那么将触发一次量子共振，Y 同学可以收集到 $1$ 个单位的量子能量。如果不存在任何关联，则该次激活不会产生能量。

Y 同学希望最大化他能收集到的总量子能量。请你帮他计算出，在所有可能的激活顺序中，最多能够获得多少个单位的量子能量。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示量子节点的数量和潜在纠缠关联的对数。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示量子节点 $u$ 和量子节点 $v$ 之间存在一对潜在的纠缠关联。

输出格式

输出一行一个整数，表示 Y 同学最多能获得的量子能量总数。

样例

样例输入 #1

3 3
1 2
2 3
1 3

样例输出 #1

2

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$，$0 \le m \le 2 \times 10^5$。保证给定的无向图中不存在自环和重边。

• 特殊性质 A：保证 $m = 0$。
• 特殊性质 B：保证给定的无向图 $G$ 是一棵树或由若干棵树组成的森林。