trang chủ / đề bài / icpcwf15_k

Các tuyến du lịch

Đề bài

Mô tả

Vườn quốc gia Arca Carania sắp mở cửa đón khách du lịch. Vườn quốc gia có một số điểm tham quan và các con đường nối từng cặp điểm tham quan. Ban quản lý vườn đã lập ra một tập các tuyến du lịch vòng tròn, trong đó du khách đi xe buýt để ngắm các điểm tham quan. Mỗi tuyến vòng tròn bắt đầu tại một điểm nào đó (các tuyến khác nhau có thể bắt đầu ở các điểm khác nhau), đi qua một số điểm khác mà không lặp lại điểm nào, rồi quay về điểm xuất phát. Mỗi tuyến vòng tròn đi qua ít nhất 3 điểm tham quan khác nhau. Trong vườn quốc gia có ít nhất một tuyến vòng tròn khả thi.

Ban quản lý quyết định rằng với mỗi con đường, mọi xe buýt chạy trên đường đó do cùng một công ty vận hành. Ban quản lý không muốn bị cho là thiên vị, nên muốn chắc chắn rằng trên mỗi tuyến vòng tròn khả thi trong vườn, số con đường được giao cho mỗi công ty xe buýt là như nhau. Họ biết rằng điều này có thể khó đạt được. Vì vậy họ muốn biết với những số lượng công ty xe buýt nào thì tồn tại một cách giao các con đường cho các công ty thỏa mãn yêu cầu.

Nói cách khác: cho một đồ thị vô hướng đơn có ít nhất một chu trình. Một tuyến vòng tròn là một chu trình đơn (không lặp đỉnh) có ít nhất 3 đỉnh. Hãy tìm mọi số nguyên k sao cho có thể tô mỗi cạnh bằng một trong k màu để trên mọi chu trình đơn, số cạnh của mỗi màu đều bằng nhau.

Xét ví dụ 1, đồ thị được vẽ dưới đây. Có tất cả ba tuyến vòng tròn. Con đường 1-3 được giao cho một công ty nào đó. Công ty này cũng phải được giao một con đường trên tuyến 1-2-3-4-1, chẳng hạn 2-3. Nhưng khi đó công ty này được giao hai trong ba con đường của tuyến 1-2-3-1, và không công ty nào khác có thể bằng được, nên không thể có công ty nào khác.

graph
4 5
1 2
2 3
3 4
1 4
1 3
pos 1 0 120
pos 2 0 0
pos 3 120 0
pos 4 120 120

Ở ví dụ 2 chỉ có một tuyến vòng tròn, nên chỉ cần chia đều các con đường của tuyến này cho các công ty.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và m, lần lượt là số điểm tham quan và số con đường.

Tiếp theo là m dòng, mỗi dòng chứa hai số nguyên ai và bi, cho biết có một con đường hai chiều nối điểm ai và điểm bi. Không có cặp điểm nào được liệt kê hai lần.

Dữ liệu ra

In ra mọi số nguyên k sao cho có thể giao các con đường cho k công ty theo yêu cầu, theo thứ tự tăng dần, trên một dòng, cách nhau bởi dấu cách.

Ràng buộc

  • 1≤n≤2000, 1≤m≤2000.
  • 1≤ai<bi≤n.
  • Không có cặp điểm nào được liệt kê hai lần, và đồ thị có ít nhất một chu trình.

Ví dụ

Input Output Giải thích
4 5
1 2
2 3
3 4
1 4
1 3
1 Ba tuyến vòng tròn 1-2-3-1, 1-3-4-1, 1-2-3-4-1: chỉ có thể dùng một công ty.
6 6
1 2
2 3
1 3
1 4
2 5
3 6
1 3 Chỉ có một tuyến vòng tròn 1-2-3-1 gồm 3 con đường; các con đường 1-4, 2-5, 3-6 không thuộc tuyến nào nên giao tùy ý. Có thể dùng 1 hoặc 3 công ty.

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