trang chủ / bài tập / pairs

Cặp số

Cho $m$ cặp số nguyên, mỗi số nằm trong đoạn từ $1$ đến $n$ . Các cặp là $(a_{1}, b_{1}), (a_{2}, b_{2}), \dots, (a_{m}, b_{m})$ .

Hãy kiểm tra xem có tồn tại hai số nguyên $x$ và $y$ (với $1 \leq x < y \leq n$ ) sao cho trong mỗi cặp đã cho, có ít nhất một số bằng $x$ hoặc bằng $y$ hay không.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ : cận trên của các giá trị và số cặp.
$m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_{i}$ và $b_{i}$ : hai số trong cặp thứ $i$ .

Dữ liệu ra

In ra YES nếu tồn tại hai số $x$ và $y$ thỏa mãn, ngược lại in ra NO.

Ràng buộc

$2 \leq n \leq 300 000$
$1 \leq m \leq 300 000$
$1 \leq a_{i}, b_{i} \leq n$ và $a_{i} \neq b_{i}$

Ví dụ

Input	Output	Giải thích
4 6 1 2 1 3 1 4 2 3 2 4 3 4	NO	Không thể chọn được $x, y$ nào: với mọi cách chọn đều tồn tại một cặp mà cả hai số đều khác $x$ và $y$ .
5 4 1 2 2 3 3 4 4 5	YES	Có thể chọn $x = 2$ và $y = 4$ : cặp $(1, 2)$ chứa $2$ , cặp $(2, 3)$ chứa $2$ , cặp $(3, 4)$ chứa $4$ , cặp $(4, 5)$ chứa $4$ .
300000 5 1 2 1 2 1 2 1 2 1 2	YES	Có thể chọn $x = 1$ và $y = 2$ , mọi cặp đều chứa cả hai.

Bình luận

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

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 4,00một phần

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

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

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig