Cutlet
Contest: Codeforces Round 464 (Div. 2)
Difficulty rating: 2400
Tags: data structures, dp

Arkady wants to have a dinner. He has just returned from a shop where he has bought a semifinished cutlet. He only needs to fry it. The cutlet should be fried for 2n seconds, in particular, it should be fried for n seconds on one side and n seconds on the other side. Arkady has already got a frying pan and turn on fire, but understood that maybe he won't be able to flip the cutlet exactly after n seconds after the beginning of cooking.

Arkady is too busy with sorting sticker packs in his favorite messenger and can flip the cutlet only in some periods of time. Namely, there are k periods of time in which he can do it, the i-th of them is an interval of time from li seconds after he starts cooking till ri seconds, inclusive. Arkady decided that it's not required to flip the cutlet exactly in the middle of cooking, instead, he will flip it several times in such a way that the cutlet will be fried exactly n seconds on one side and n seconds on the other side in total.

Help Arkady and find out if it's possible for him to cook the cutlet, if he is able to flip the cutlet only in given periods of time; and if yes, find the minimum number of flips he needs to cook the cutlet.

Input format:
The first line contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 100) — the number of seconds the cutlet should be cooked on each side and number of periods of time in which Arkady can flip it.

The next k lines contain descriptions of these intervals. Each line contains two integers li and ri (0 ≤ li ≤ ri ≤ 2·n), meaning that Arkady can flip the cutlet in any moment starting from li seconds after the beginning of cooking and finishing at ri seconds after beginning of cooking. In particular, if li = ri then Arkady can flip the cutlet only in the moment li = ri. It's guaranteed that li > ri - 1 for all 2 ≤ i ≤ k.

Output format:
Output "Hungry" if Arkady won't be able to fry the cutlet for exactly n seconds on one side and exactly n seconds on the other side.

Otherwise, output "Full" in the first line, and the minimum number of times he should flip the cutlet in the second line.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first example Arkady should flip the cutlet in time moment 3 seconds after he starts cooking and in time moment 13 seconds after he starts cooking.

In the second example, Arkady can flip the cutlet at 10 seconds after he starts cooking.

Example input:
10 2
3 5
11 13

Example output:
Full
2

Example input:
10 3
3 5
9 10
11 13

Example output:
Full
1

Editorial:
Let's use dynamic programming approach. Solve the following subproblem: let t be the seconds passed since the start of cooking, and t0 seconds among them the cutlet was preparing on the current side; what is the minimum number of flips needed to reach this state? This can be easily computed using answers for subproblems (t - 1, t0), (t - 1, t0 - 1), in which the cutlet lays on the same side, and (t - 1, t - 1 - t0) and (t - 1, t - t0), in which the cutlet lays on the other side. You should carefully consider the number of flips needed for each transition, and check if it is possible, according to Arkady's availability. The complexity of this solution is O(n2), which is not enough.
For full solution, it is enough to consider only moments that correspond to start of some segment Arkady's availability, because between these moments we can make at most two flips, otherwise the result is obviously not optimal. In such case to compute the answer for subproblem (t = li, t0) it is enough to compute minimum among answers for subproblems (t' = li - 1, t'0), where t' — the time of the start of the previous time segment — is fixed, and t'0 changes within several segments, the bounds of which depend on the number of flips between moments li - 1 and li seconds, and parameters li - 1, ri - 1, li, t0. For effective computing of minimums you can use the queue of minimums, because the bounds of the segments increase with the increase of t0. The total complexity is O(nk). You can also use other data structures for computing minimum, and the complexity of such solutions is $${ \mathcal { O } } ( n k \log ( n ) )$$.