trang chủ / đề bài / icpcwf19_e

Phát hiện đường cụt

Đề bài

Mô tả

Hội đồng thành phố quê bạn quyết định cải thiện việc đặt biển báo giao thông, đặc biệt là biển báo đường cụt. Họ đưa cho bạn bản đồ đường phố và bạn phải xác định cần đặt biển ở đâu để đánh dấu các đường cụt. Họ muốn dùng càng ít biển càng tốt.

Bản đồ gồm một tập các địa điểm được nối với nhau bởi các con đường hai chiều. Quy tắc sau mô tả cách thu được một phương án đặt biển báo đường cụt đầy đủ. Xét một con đường S nối địa điểm x với một địa điểm khác. Lối vào phía x của S được đặt biển báo đường cụt nếu sau khi đi vào S từ x, không thể quay trở lại x mà không quay đầu xe. Quay đầu xe là một lượt quay 180 độ, đổi ngược ngay lập tức hướng đi.

Để tiết kiệm chi phí, bạn quyết định không đặt các biển báo thừa, theo quy tắc sau. Xét một con đường S có biển báo đường cụt ở lối vào phía x và một con đường T khác có biển báo đường cụt ở lối vào phía y. Nếu sau khi đi vào S từ x, có thể đi tới y và đi vào T (từ phía y) mà không quay đầu xe, thì biển báo ở lối vào phía y của T là thừa.

Hình dưới minh họa hai ví dụ. Các con đường tô đỏ là những con đường được đặt biển báo không thừa; vị trí của biển (đầu nào của con đường) ghi trong cột Giải thích của bảng ví dụ.

graph
6 5
1 2
1 3
2 3
4 5
5 6
highlight red 4-5 5-6
graph
8 8
1 2
1 3
2 3
3 4
1 5
1 6
6 7
6 8
highlight red 1-5 1-6 3-4

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và m, trong đó n là số địa điểm và m là số con đường.

Mỗi dòng trong m dòng tiếp theo chứa hai số nguyên v và w cho biết có một con đường hai chiều nối địa điểm v và địa điểm w. Mọi cặp địa điểm trong dữ liệu vào đều khác nhau.

Dữ liệu ra

Dòng đầu tiên in ra k, số biển báo đường cụt được đặt.

Mỗi dòng trong k dòng tiếp theo in ra hai số nguyên v và w, cho biết một biển báo đường cụt được đặt ở lối vào phía v của con đường nối hai địa điểm v và w. Các dòng mô tả biển báo phải được sắp xếp tăng dần theo v, nếu bằng nhau thì tăng dần theo w.

Ràng buộc

  • 1≤n≤5·105.
  • 0≤m≤5·105.
  • 1≤v<w≤n.

Ví dụ

Input Output Giải thích
6 5
1 2
1 3
2 3
4 5
5 6
2
4 5
6 5
Từ các địa điểm 1,2,3 luôn có thể đi vòng quanh tam giác để quay lại. Đi vào đường 4-5 từ 4 thì phải quay đầu ở 6 mới về được 4, nên lối vào phía 4 có biển; tương tự lối vào phía 6 của đường 5-6. Biển ở lối vào phía 5 của hai con đường này là thừa: từ 4 đi vào đường 4-5 có thể tới 5 rồi đi vào đường 5-6.
8 8
1 2
1 3
2 3
3 4
1 5
1 6
6 7
6 8
3
1 5
1 6
3 4
Biển đặt ở lối vào phía 1 của các đường 1-5, 1-6 và lối vào phía 3 của đường 3-4. Biển ở lối vào phía 6 của các đường 6-7, 6-8 là thừa vì có thể đi từ 1 vào đường 1-6 rồi đi tiếp vào chúng.

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