trang chủ / đề bài / icpc24_mb_h

In tài liệu

Đề bài

Mô tả

Khi in tài liệu, tiến sĩ Lecter nhận ra các trang ông in ra hoàn toàn lộn xộn. Tài liệu có N trang, đánh số từ 1 đến N. Đã có tổng cộng M tờ giấy được in, tờ thứ i chứa nội dung của hai trang ai và bi, mỗi trang ở một mặt của tờ giấy (tờ giấy có thể lật tùy ý nên trang ai hoặc trang bi đều có thể đứng trước). Vì việc in rất tốn thời gian và số tờ giấy trắng còn lại có hạn, tiến sĩ Lecter muốn tìm số tờ giấy ít nhất cần in thêm (mỗi tờ in hai trang tùy chọn lên hai mặt) để có thể sắp xếp một tập con các tờ giấy thành một tài liệu dùng được. Vì tài liệu này chỉ do tiến sĩ Lecter sử dụng, chỉ cần tồn tại dãy chỉ số i1<i2<…<iN sao cho trang thứ ij trong tài liệu (đọc lần lượt từng mặt của các tờ theo thứ tự đã xếp) có nội dung trang số j (1≤j≤N) là tài liệu dùng được.

Ví dụ, với N=4, M=2 và hai tờ đã in: tờ thứ nhất chứa hai trang (1,4), tờ thứ hai chứa hai trang (3,3). Khi đó tiến sĩ Lecter chỉ cần in thêm một tờ chứa các trang (1,2). Xếp các tờ theo thứ tự (1,2),(3,3),(4,1), ông có một tài liệu dùng được (các trang thứ 1,2,3,5 của tài liệu tạo thành dãy đầy đủ các trang 1,2,3,4).

Yêu cầu: Hãy giúp tiến sĩ Lecter tìm số tờ giấy ít nhất cần in thêm để tạo được một tài liệu dùng được.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên N và M (1≤N≤400, 0≤M≤105).
  • Dòng thứ i trong M dòng tiếp theo chứa hai số nguyên ai và bi (1≤ai,bi≤N).

Dữ liệu ra

In ra một số nguyên là số tờ giấy ít nhất cần in thêm để tạo được một tài liệu dùng được.

Ràng buộc

  • 1≤N≤400
  • 0≤M≤105
  • 1≤ai,bi≤N

Ví dụ

Input Output Giải thích
4 2
1 4
3 3
1 In thêm tờ (1,2) và xếp các tờ theo thứ tự (1,2),(3,3),(4,1).
3 2
3 2
2 2
1 Không dùng tờ (2,2). Lật tờ (3,2) thành (2,3), in thêm một tờ chứa hai trang (1,1) (hoặc (1,2), (1,3) cũng được) và đặt nó trước tờ (2,3).
5 3
2 3
4 5
1 4
0 Không cần in thêm: xếp các tờ có sẵn theo thứ tự (1,4),(2,3),(4,5).

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0