T841032 栈道分段（bridge）

景区中有 $n$ 个观景平台，从左到右依次编号为 $1,2,\ldots,n$。对于每个 $1\le i

第一行包含一个整数 $T$，表示数据组数。接下来依次给出每组数据。 每组数据的第一行包含两个整数 $n,m$，分别表示平台数量和要求数量。 接下来 $m$ 行，每行包含两个整数 $a_j,b_j$，表示一条要求。保证 $a_j

对每组数据输出一行一个整数，表示最少需要关闭的栈道数量。

关闭平台 $2$ 与平台 $3$ 之间的栈道后，平台 $1,2$ 位于同一个区域，平台 $3,4,5$ 位于另一个区域。此时平台 $1$ 无法到达平台 $4$，平台 $2$ 也无法到达平台 $5$，两条要求均被满足。 如果不关闭任何栈道，所有平台仍然连通，无法满足要求。因此答案为 $1$。 ## 样例 2 见 `考生目录/bridge/bridge2.in` 与 `考生目录/bridge/bridge2.ans`。该样例满足测试点 $1\sim6$ 的约束。 ## 样例 3 见 `考生目录/bridge/bridge3.in` 与 `考生目录/bridge/bridge3.ans`。该样例满足测试点 $7\sim12$ 的约束。 ## 样例 4 见 `考生目录/bridge/bridge4.in` 与 `考生目录/bridge/bridge4.ans`。该样例满足测试点 $13\sim20$ 的约束。 ## 样例 5 见 `考生目录/bridge/bridge5.in` 与 `考生目录/bridge/bridge5.ans`。该样例满足测试点 $13\sim20$ 的约束。 ## 样例 6 见 `考生目录/bridge/bridge6.in` 与 `考生目录/bridge/bridge6.ans`。该样例满足测试点 $13\sim20$ 的约束。 ## 数据范围 对于所有数据，保证： - $1\le T\le10$； - 每组数据中，$2\le n\le10^5$，$1\le m\le\min\{10^5,n(n-1)/2\}$； - $1\le a_j