408702: GYM103265 E Котлета

E. Котлетаограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Аркадий хочет обедать. Он только что вернулся из магазина, где приобрел полуфабрикат — котлету, которую осталось только поджарить. Надпись на упаковке гласит, что котлету нужно жарить на сковороде на умеренном огне ровно 2n секунд, причем сначала нужно ровно n секунд жарить котлету на одной стороне, а затем ровно n секунд — на другой. Аркадий уже нашел сковороду и зажег умеренный огонь, но тут осознал, что, возможно, у него не получится перевернуть котлету ровно через n секунд после начала готовки.

Аркадий слишком занят расстановкой по порядку наборов стикеров в своем любимом мессенджере, и может отвлечься на переворот котлеты только в определенные моменты времени. А именно, есть k промежутков времени, в которые он может это сделать, i-й из них — это отрезок времени с l_i секунд от начала готовки до r_i секунд до начала готовки, включительно. Аркадий решил, что не обязательно переворачивать котлету ровно в середине готовки, вместо этого, он перевернет ее несколько раз таким образом, чтобы суммарно котлета провела n секунд на одной стороне и n секунд на другой.

Помогите Аркадию, узнайте, может ли он выполнить свой план, если он может переворачивать котлету только в указанные отрезки времени, и если да, то какое минимальное число раз ему придется перевернуть котлету.

Входные данные

Первая строка содержит два целых числа n и k (1 ≤ n ≤ 500 000, 1 ≤ k ≤ 100) — число секунд, которое котлета должна жариться с каждой из сторон, и число промежутков времени, когда Аркадий может ее переворачивать.

Следующие k строк содержат описания этих промежутков. Каждая строка содержит два целых числа l_i и r_i (0 ≤ l_i ≤ r_i ≤ 2·n), что означает, что Аркадий может перевернуть котлету в любой момент времени, начиная с l_i секунд от начала готовки и заканчивая r_i секундами от начала готовки, включительно. В частности, если l_i = r_i, то Аркадий может перевернуть котлету в момент времени l_i = r_i. Гарантируется, что l_i > r_i - 1 для всех 2 ≤ i ≤ k.

Выходные данные

Выведите в единственную строку «Hungry», если Аркадий не может пожарить котлету ровно n секунд на одной стороне и ровно n секунд на другой.

В противном случае, выведите в первую строку «Full», а во вторую — минимальное количество раз, которое ему необходимо перевернуть котлету.

Система оценки

Тесты, в которых в правильном ответе котлету нужно переворачивать не более двух раз, или Аркадий не может пожарить котлету требуемым образом, имеют суммарную стоимость не менее 30 баллов.

Тесты, в которых n ≤ 1000, имеют суммарную стоимость не менее 40 баллов.

ПримерыВходные данные

10 2
3 5
11 13

Выходные данные

Full
2

Входные данные

10 3
3 5
9 10
11 13

Выходные данные

Full
1

Входные данные

20 1
3 19

Выходные данные

Hungry

Примечание

В первом примере котлету нужно перевернуть в моменты времени 3 секунды после начала и 13 секунд после начала.

Во втором примере котлету можно перевернуть, как и написано на упаковке, через 10 секунд после начала.