B. Ктулху

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

... Эрт урьдын цагт нэгэн залуу тэнгисийн хүрч иржээ. Тэнгис шуургатай бас харанхуй байлаа. Залуу лусын дагиныг дуудаж эхэлсэн боловч харамсалтай нь тэр Ктулхуг сэрээсэн байлаа...

Дэлхийн төгсгөл тун ойртжээ. Пентагоны мангасын зан аашыг судлаад түүнд тохируулан бэлдсэн нууц супер зэвсэг л эцсийн найдвар байв.

Газар хөдлөлт эрчимжиж, цаг агаар тогтворгүй болсон тул хиймэл дагуулууд мангасыг тийм ч оновчтой тодорхойлж чадахгүй байлаа. Эхний оролдлогоор тэд $n$ орой, $m$ ирмэг бүхий чиглэл граф бүхий мэдээллийг олж авав. Одоо дэлхийн бүх оюун ухааны салбарын шилдгүүд цуглаад энэ дүрслэгдсэн граф нь Ктулху мангас мөн эсэхийг тогтоох гэж байв.

Хялбарчлахын тулд, Ктулхуг сансраас харах үед бие бөөрөнцөг хэлбэртэй харагдах ба биед нь тэмтрүүлүүд холбогдсон гэж үзье. Тэгэхлээр Ктулху нь гурав болон түүнээс дээших өлгөгдсөн моднууд олонлог хэлбэрээр дүрслэгдэнэ. Бас энэ моднуудын үндэснүүд нь "энгийн цикл"-ээр холбогдсон байна.

![][1]

Оролт

Эхний мөрөнд графын оройн тоо $n$, ирмэгийн тоо $m$ ($1 ≤ n ≤ 100$; $0 ≤ m ≤ \ $![][2]).

Дараагийн $m$ мөрөнд мөр бүрд $x$, $y$ ($1 ≤ x, y ≤ n; x ≠ y$) хос тоонууд байрлана. Энэ нь $x$, $y$ болон дугаартай хоёр орой хоорондоо ирмэгээр холбогдсонг илтгэнэ. Аль ч хоёр оройн хооронд хамгийн ихдээ нэг л ирмэг байна.

Гаралт

Хэрвээ энэ граф Ктулху мөн байвал "FHTAGN!" гэж биш байвал "NO" гэж хэвлэнэ.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
6 6
6 3
6 4
5 1
2 5
1 4
5 4
Гаралт
FHTAGN!
Оролт
6 5
5 6
4 6
3 1
5 1
1 2
Гаралт
NO

Тэмдэглэл

"Энгийн цикл" гэж $v$ ирмэгүүдтэй бөгөөд эдгээр нь харгалзан $1$ ба $2$, $2$ ба $3$, ... , $v-1$ ба $v$, $v$ ба $1$ гэх мэт оройнуудыг холбосон байхыг хэлнэ.

Мод гэдэг нь $n$ ($n > 0$) ирмэг $n-1$ оройноос тогтох чиглэлгүй, холбогдсон граф.

Өлгөгдсөн мод гэдэг нь модны нэг оройг үндэс болгон сонгож аваад модыг энэ оройноос өлгөж "унжуулсныг" хэлнэ.

Сэтгэгдлүүдийг ачааллаж байна...