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

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:ASM32-GCC MAWK BC C-CLANG C CPP C++ 4.3.2 CPP14-CLANG CPP14 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PAS-GPC PAS-FPC PICO PROLOG PY_NBC R RACKET CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Nguồn bài:Nguyễn Xuân Khánh

hide comments
2016-12-23 05:14:43 hồ vãn tuấn
Floyd kiểu gì nhỉ?
2016-06-07 16:32:42
Floyd =)))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.