Cthulhu

Điểm: 4,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Một vệ tinh chụp được hình ảnh quái vật Cthulhu và phân tích nó thành một đồ thị vô hướng có $N$ đỉnh và $M$ cạnh. Người ta định nghĩa Cthulhu trông giống một "thân hình cầu có các xúc tu" — về mặt hình thức, đó là đồ thị có thể được biểu diễn dưới dạng một tập hợp gồm ba hoặc nhiều cây có gốc, trong đó các gốc được nối với nhau thành một chu trình đơn.

Cho đồ thị (không có khuyên, không có cạnh bội), hãy xác định xem đồ thị có phải là Cthulhu hay không.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $M$ — số đỉnh và số cạnh của đồ thị.
$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $y$ ( $1 \leq x, y \leq N$ , $x \neq y$ ) cho biết có một cạnh giữa đỉnh $x$ và đỉnh $y$ .

Đảm bảo không có cạnh bội và không có khuyên.

Dữ liệu ra

In ra FHTAGN! nếu đồ thị là Cthulhu, ngược lại in ra NO.

Ràng buộc

$1 \leq N \leq 100$
$0 \leq M \leq \frac{N (N - 1)}{2}$

Ví dụ

Input	Output	Giải thích
6 6 6 3 6 4 5 1 2 5 1 4 5 4	FHTAGN!	Đồ thị liên thông, có đúng 6 cạnh và 6 đỉnh, trong đó các đỉnh 1, 4, 5 tạo thành chu trình; các đỉnh 2, 3, 6 là các "xúc tu".
6 5 5 6 4 6 3 1 5 1 1 2	NO	Đồ thị không liên thông (đỉnh 3 không nối được tới đỉnh 6), nên không phải Cthulhu.

Bình luận

Không có bình luận tại thời điểm này.