Chụp Ảnh Đàn Bò

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

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

Có $N$ con bò đứng thành một hàng, đánh số từ $1$ đến $N$ . Cần chụp ảnh toàn bộ đàn bò, mỗi tấm ảnh chụp một đoạn liên tiếp các con bò. Mỗi con bò phải xuất hiện trong ít nhất một tấm ảnh.

Có $K$ cặp bò không thân thiện — hai con bò trong một cặp không được cùng xuất hiện trong cùng một tấm ảnh.

Tìm số tấm ảnh tối thiểu cần chụp để thỏa mãn tất cả điều kiện.

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $K$
$K$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $A_{i}$ và $B_{i}$ — cặp bò không thân thiện ( $A_{i} \neq B_{i}$ )

Dữ liệu ra

Một số nguyên — số tấm ảnh tối thiểu cần chụp.

Ràng buộc

$2 \leq N \leq 10^{9}$
$1 \leq K \leq 1000$
$1 \leq A_{i}, B_{i} \leq N$

Ví dụ

Input	Output	Giải thích
7 3 1 3 2 4 5 6	3	Ba ảnh: bò 1–2, bò 3–5, bò 6–7. Không có cặp thù địch nào cùng ảnh.
100 50 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1	51	Mỗi cặp bò liên tiếp lẻ-chẵn buộc phải ở ảnh riêng.

Bình luận

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