1524：旅游航道

题目描述

SGOI 旅游局在 SG-III 星团开设了旅游业务，每天有数以万计的地球人来这里观光，包括联合国秘书长，各国总统和 SGOI 总局局长等。旅游线路四通八达，每天都有众多的载客太空飞船在星团的星球之间来往穿梭，他们保证了任意两个星球之间总是可以通过航道到达。

但是，最近由于财政出现了困难，一些太空飞船也过于古老，又没有足够的资金购买新产品，所有只好取消一些航道。如果某一条航道的删除使得一些星球不能到达，那么这条航道是不能删除的，称之为「主要航道」。

SGOI 旅游局局长希望知道主要航道的数目，但是航道较多，他不能手工计算，于是，他委托你写一个程序，计算主要航道数目。

输入格式

输入包含若干组数据。

每组数据的首行有两个数 $m, n$。星球的编号从 $1$ 到 $m$。

以下 $n$ 行每行用两个整数 $a, b$ 描述一条航道的信息，表示从星球 $a$ 到星球 $b$ 是有航道的（航道是双向的）。数据由 SGOI 旅游局提供，你无需担心数据有错。

输入文件以一行 0 0 为结束。

输出格式

输出共有 $C$ 行，第 $i$ 行仅有一个数，表示第 $i$ 组输入数据的主要行道数目。

样例

样例输入 #1

2 1
1 2
0 0

样例输出 #1

1

样例解释 #1

• $m=2$ 个星球，$n=1$ 条航道。
• 航道：$1-2$（双向）。
• 删除这条航道后，星球 $1$ 和 $2$ 不连通，所以它是主要航道。
• 主要航道数目为 $1$。

数据范围

• $1 \le m \le 30000$
• $1 \le n \le 30000$
• $1 \le a, b \le m$

时空限制

• 时间限制：1000 ms
• 内存限制：562144 KB

注意：本题是求无向连通图中桥（割边）的数量。因为题目保证任意两个星球之间总是可以通过航道到达，所以图是连通的（每组数据都是连通图）。使用 Tarjan 算法求桥：对于边 $(u, v)$（在 DFS 树中 $u$ 是 $v$ 的父节点），如果 $low[v] > dfn[u]$，则 $(u, v)$ 是桥。注意要处理重边（如果两点间有多条边，则这些边都不是桥）。由于 $m, n$ 可达 $30000$，需要使用邻接表存储，并注意在 DFS 时避免重复访问。多组数据直到 $m=0, n=0$ 结束。