Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMLP - Đường đi dài nhất

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vmlp


Bạn được nhận xử lý một đồ thị. Đồ thị này được gọi là đơn đồ thị vô hướng, tức là giữa hai đỉnh u và v bất kì chỉ có tối đa một cung nối vô hướng.

Một đường đi đơn trên đồ thị là một dãy các đỉnh x1, x2, ..., xk sao cho luôn có cung nối giữa đỉnh xi và đỉnh xi + 1(1 ≤ i < k). Đường đi đơn là đường đi mà không có hai đỉnh nào lặp lại.

Độ dài đường đi là số đỉnh trên đường đi đó. Hãy tìm một đường đi đơn có độ dài lớn nhất có thể trên đồ thị đã cho.

Input

Input gồm nhiều dòng:

  • Dòng thứ nhất: 2 số nguyên N và M, số đỉnh và số cạnh của đồ thị.
  • M dòng tiếp theo: mỗi dòng ghi hai số nguyên u và v (u khác v), thể hiện cạnh (u, v) vô hướng trong đồ thị.

Output

Ouput gồm 2 dòng:

  • Dòng thứ nhất là một số nguyên, độ dài đường đi đơn tìm được.
  • Dòng thứ hai là dãy các đỉnh thể hiện đường đi đó.

Giới hạn

  • N ≤ 1000, M ≤ 10000.

Cách tính điểm

Điểm tạm thời của thí sinh X (TPx) được tính theo công thức sau: gọi R là tỉ số giữa đáp án của thí sinh X và đáp án của ban tổ chức,

  • Nếu R < 0.8: TPx = 100R;
  • Nếu 0.8 ≤ R ≤ 1: TPx = 40 + 60(R - 0.8) / 0.2;
  • Nếu R > 1: TPx = 100 + 100R / 3.

Điểm chính thức của thí sinh X (OPx) được tính theo công thức sau: gọi TPmax là điểm tạm thời cao nhất trong điểm tạm thời của các thí sinh:

  • OPx = TPx / TPmax * 100.

Example

Input:
6 5
1 2
2 3
3 4
2 5
5 6

Output: 5
4 3 2 5 6

Lời giải trên sẽ được 100.0 điểm (chính thức) vì đường đi đã tìm được là tối ưu.

Lưu ý: lời giải của bạn sẽ được chấm thử trên 10 test (không bao gồm test đề) trong suốt thời gian diễn ra vòng thi này. Bộ test chính thức sẽ có nhiều test hơn và bao gồm cả 10 test trên.


Được gửi lên bởi:VOJ Team
Ngày:2012-05-26
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP PAS-GPC PAS-FPC
Nguồn bài:Nguyễn Xuân Khánh

hide comments
2020-11-13 04:53:10 Pham Dat
đồ thị vô hướng nhưng dùng sai khái niệm cung/cạnh. admin nên cập nhật lại đề.
2019-05-15 13:04:06
⠄⠄⠄⣾⣿⠿⠿⠶⠿⢿⣿⣿⣿⣿⣦⣤⣄⢀⡅⢠⣾⣛⡉⠄⠄⠄⠸⢀⣿
⠄⠄⢀⡋⣡⣴⣶⣶⡀⠄⠄⠙⢿⣿⣿⣿⣿⣿⣴⣿⣿⣿⢃⣤⣄⣀⣥⣿⣿
⠄⠄⢸⣇⠻⣿⣿⣿⣧⣀⢀⣠⡌⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⣿⣿⣿
⠄⢀⢸⣿⣷⣤⣤⣤⣬⣙⣛⢿⣿⣿⣿⣿⣿⣿⡿⣿⣿⡍⠄⠄⢀⣤⣄⠉⠋
⠄⣼⣖⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⢇⣿⣿⡷⠶⠶⢿⣿⣿⠇⢀
⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⡇⣿⣿⣿⣿⣿⣿⣷⣶⣥⣴⣿
⢀⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟
⢸⣿⣦⣌⣛⣻⣿⣿⣧⠙⠛⠛⡭⠅⠒⠦⠭⣭⡻⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃
⠘⣿⣿⣿⣿⣿⣿⣿⣿⡆⠄⠄⠄⠄⠄⠄⠄⠄⠹⠈⢋⣽⣿⣿⣿⣿⣵⣾⠃
⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿⠄⣴⣿⣶⣄⠄⣴⣶⠄⢀⣾⣿⣿⣿⣿⣿⣿⠃⠄
⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿⡄⢻⣿⣿⣿⠄⣿⣿⡀⣾⣿⣿⣿⣿⣛⠛⠁⠄⠄
2019-05-14 11:20:16
chao con cac
2019-05-14 11:19:53
..................……………………….…._¸„„„„_
…………………….…………...„--~*'¯….….'\
………….…………………… („-~~--„¸_….,/ì'Ì
…….…………………….¸„-^"¯ : : : : :¸-¯"¯/'
……………………¸„„-^"¯ : : : : : : : '\¸„„,-"
**¯¯¯'^^~-„„„----~^*'"¯ : : : : : : : : : :¸-"
.:.:.:.:.„-^" : : : : : : : : : : : : : : : : :„-"
:.:.:.:.:.:.:.:.:.:.: : : : : : : : : : ¸„-^¯
.::.:.:.:.:.:.:.:. : : : : : : : ¸„„-^¯
:.' : : '\ : : : : : : : ;¸„„-~"¯
:.:.:: :"-„""***/*'ì¸'¯
:.': : : : :"-„ : : :"\
.:.:.: : : : :" : : : : \,
:.: : : : : : : : : : : : 'Ì
: : : : : : :, : : : : : :/
"-„_::::_„-*__„„~"
2019-05-14 11:10:03
tran duc manh xin chao hoang nghia hiep
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.