There are N trees in a particular region of forest with the trees number from 1 to N. Tarzan, our hero is standing on Tree Number 1. Tarzan wants to have a sea view from the top of a tree to see whether his girlfriend has arrived at the shore or not. But the shore is visible only from tree number N.

So, he needs to reach tree number N without climbing down from any of the tree.. He can jump from any tree to any other tree except for some pairs of trees which are not close enough. Also, all the other trees in the forest except for these N trees are too far away from these N trees, which means he CANNOT jump from one of the N trees to any tree which is not part of the given set. (N trees).

If it is not possible to reach tree N by the above method, you should print “HOHA HOHA” (without quotes) which is how Tarzan shows his frustration. If it is possible to reach tree N, then print a single integer representing the minimum number of jumps for the same.

Input format : First line has two integers N and M, N the number of trees, and M, the number of trees which are not close enough (1 <= N <= 1000, M <= 1000000). The next M lines contains two integers t1 and t2 each which means the pair t1 and t2 are not close enough. (1 <= t1, t2 <= N).

Output format : If it is possible to reach tree N, then print a single integer representing the minimum number of jumps for the same. Else print “HOHA HOHA”.

Setter : SP Harish