时间限制： 1.0 秒

空间限制： 512 MB

题目描述

请利用图的广度优先遍历找出图的最小环，若不存在环请输出 $+\infty$。若图中有 $n$ 个点和 $m$ 条边，要求时间复杂度为 $O(n(n+m))$，空间复杂度 $O(n+m)$。最小环即为环上点数最少的环。

输入格式

从标准输入读入数据。

第一行两个正整数 $n,m$，表示图的点数和边数。

接下来 $m$ 行，每行两个整数 $u,v$，表示无向图中的边。

输出格式

输出到标准输出。

若图中存在环，输出一行一个整数，表示图中环上点数最小的环，你只需要输出点的个数即可。

若图中不存在环，则输出一行 inf。

3 3
1 2
2 3
3 1

3

2 1
1 2

inf

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

3

子任务

对于所有数据，保证 $n,m\le 3\times 10^3$，图中不存在重边和自环。

本题无数据梯度，需要通过全部数据获得所有分数。

提示

可以回顾一下邓俊辉《数据结构》教材 6.6 广度优先搜索部分，在所有边的边权相同的情况下，以一个点为起点做出的 BFS 树，即为单源最短路径树。

在单源构造 BFS 树的过程中，原图中会存在树边和跨边。由于树边对应单源的最短路径，我们不难得知：对于最小的环，一定是由 BFS 上的树边和跨边共同构成的。因此在 BFS 的过程中遇到跨边时，即为一个备选答案。

来源

清华 826 考研初试 2017 - 算法大题（1）