← 返回题目列表

Codeforces · 103/B

B. 克苏鲁

中文机器翻译题面 查看原题

...从前,有一个人来到了大海。大海波涛汹涌,漆黑一片。男人开始呼唤小人鱼出现,可惜,他只是吵醒了克苏鲁……

而在世界的另一端,五角大楼正在积极收集信息,试图预测怪物的行为并准备秘密超级武器。由于地震活动频繁和天气条件恶劣,卫星尚未能够清晰地拍摄到这个怪物的照片。对第一个镜头的分析产生了一个具有 n 个顶点和 m 个边的无向图。现在世界上最聪明的人即将决定这张图是否可以被视为克苏鲁。

为了简单起见,我们假设克苏鲁从太空中看起来像一些带有触手的球形物体。形式上,我们将这样的无向图视为 Cthulhu,它可以表示为一组三个或更多有根树,其根通过简单的循环连接。

保证图不包含重边和自环。

输入

第一行包含两个整数 - 图的顶点数 n 和边数 m (1 ≤ n ≤ 100, 0 ≤ m ≤ $$\frac{n \cdot (n-1)}{2}$$)。

以下 m 行中的每一行都包含一对整数 x 和 y,这表明顶点 x 和 y 之间存在一条边(1 ≤ x,y ≤ n,x ≠ y)。对于每一对顶点,它们之间最多有一条边,没有边将顶点连接到其自身。

输出

如果图形不是 Cthulhu,则打印“NO”和“FHTAGN!”如果是的话。

示例

输入 #1

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

输出 #1

FHTAGN!

输入 #2

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

输出 #2

NO

注意

让我们将一组 v 个顶点表示为一个简单循环,这些顶点可以编号,以便边仅存在于顶点编号 1 和 2、2 和 3、...、v - 1 和 v、v 和 1 之间。

树是由 n 个顶点和 n - 1 条边 (n > 0) 组成的连通无向图。

有根树是选择一个顶点作为根的树。