CF103B Cthulhu

从前有个人来到海边。大海风暴肆虐，乌云密布。那人开始呼唤小美人鱼现身，但不幸的是，他只唤醒了克苏鲁…… 与此同时，在世界的另一端，五角大楼正积极收集情报，试图预测怪物的行为，并准备秘密超级武器。由于高强度的地震活动和恶劣的天气条件，卫星尚未能拍摄到怪物的清晰照片。对第一张照片的分析得到了一个无向图，该图有 $n$ 个顶点和 $m$ 条边。现在，世界上最聪明的人们正试图判断，这个图是否可以被视为克苏鲁。 为简化问题，假设从太空中看，克苏鲁像一个带有触手的球形物体。形式化地说，我们认为“克苏鲁”是这样一种无向图：它可以表示为三棵或更多有根树的集合，这些树的根通过一个简单环连接。 保证图中没有重边和自环。 

第一行包含两个整数 $n$ 和 $m$，分别表示图的顶点数和边数（$1 \le n \le 100$，$0 \le m \le \frac{n(n-1)}{2}$）。 接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示在顶点 $x$ 和 $y$ 之间存在一条边（$1 \le x, y \le n, x \ne y$）。任意一对顶点之间最多只有一条边，且没有顶点与自身相连的边。

如果该图不是克苏鲁，输出 "NO"；如果是，输出 "FHTAGN!"。

我们称简单环为一组 $v$ 个顶点，可以编号为 $1,2,\ldots,v$，且仅在顶点 $1$ 与 $2$、$2$ 与 $3$、……、$v-1$ 与 $v$、$v$ 与 $1$ 之间存在边。 树是一个连通的无向图，包含 $n$ 个顶点和 $n-1$ 条边（$n>0$）。 有根树是指在树中选定一个顶点作为根的树。 由 ChatGPT 4.1 翻译