P10099: 恶魔克图胡
传统题
2.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】很久以前，有一个人来到海边。海上狂风暴雨，一片漆黑。这个人开始呼唤小美人鱼出现，但唉，他只唤醒了恶魔克图胡……
而在世界的另一端，五角大楼正在积极收集信息，试图预测怪物的行为，并准备秘密的超级武器。由于地震活动频繁和恶劣的天气条件，卫星还无法清晰地拍摄到这个怪物。对第一个镜头的分析产生了一个有n个顶点和m条边的无向图。现在，世界上最聪明的人将决定这张图是否可以被视为恶魔克图胡。
为了简单起见，让我们假设克图胡从空间上看起来像一个带有触手的球形物体。形式上，我们将把克图胡视为这样一个无向图，它可以表示为一组三棵或三棵以上有根的树，它们的根通过一个简单的循环连接。
保证图不包含多条边和自环。
【输入】
第一行包含两个整数，即图的顶点数n和边数m(1≤n≤100,0≤m≤)。
以下的m行每一行都包含一对整数x和y，这表明在顶点x和y之间存在一条边(1≤x,y≤n,x≠y)。对于每一对顶点，它们之间最多有一条边，没有边将顶点连接到其自身。
【输出】
如果图形不是克图胡，则打印“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)组成的连通无向图。
有根树是选择一个顶点作为根的树。
【样例输入】复制
【样例输出】 复制
【提示】
Cthulhu
...Once upon a time a man came to the sea. The sea was stormy and dark. The man started to call for the little mermaid to appear but alas, he only woke up Cthulhu...
Whereas on the other end of the world Pentagon is actively collecting information trying to predict the monster's behavior and preparing the secret super weapon. Due to high seismic activity and poor weather conditions the satellites haven't yet been able to make clear shots of the monster. The analysis of the first shot resulted in an undirected graph with n vertices and m edges. Now the world's best minds are about to determine whether this graph can be regarded as Cthulhu or not.
To add simplicity, let's suppose that Cthulhu looks from the space like some spherical body with tentacles attached to it. Formally, we shall regard as Cthulhu such an undirected graph that can be represented as a set of three or more rooted trees, whose roots are connected by a simple cycle.
It is guaranteed that the graph contains no multiple edges and self-loops.
To add simplicity, let's suppose that Cthulhu looks from the space like some spherical body with tentacles attached to it. Formally, we shall regard as Cthulhu such an undirected graph that can be represented as a set of three or more rooted trees, whose roots are connected by a simple cycle.
It is guaranteed that the graph contains no multiple edges and self-loops.
Input
The first line contains two integers − the number of vertices n and the number of edges m of the graph (1≤n≤100, 0≤m≤
). Each of the following m lines contains a pair of integers x and y, that show that an edge exists between vertices x and y (1≤x,y≤n,x≠y). For each pair of vertices there will be at most one edge between them, no edge connects a vertex to itself.
Output
Print "NO", if the graph is not Cthulhu and "FHTAGN!" if it is.
Examples
Input
6 6 6 3 6 4 5 1 2 5 1 4 5 4
Output
FHTAGN!
Input
6 5 5 6 4 6 3 1 5 1 1 2
Output
NO
Note
Let us denote as a simple cycle a set of v vertices that can be numbered so that the edges will only exist between vertices number 1 and 2, 2 and 3, ..., v-1 and v, v and 1. A tree is a connected undirected graph consisting of n vertices and n-1 edges (n>0).
A rooted tree is a tree where one vertex is selected to be the root.