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

Giới hạn
  • Thời gian: 0.4s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/272940/problem/W

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 x 1 , x 2 , ..., x k sao cho luôn có cung nối giữa đỉnh x i và đỉnh x i + 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 (TP x ) đượ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: TP x = 100 R ;
  • Nếu 0.8 ≤ R ≤ 1: TP x = 40 + 60 (R - 0.8) / 0.2 ;
  • Nếu R > 1: TP x = 100 + 100 R / 3 .

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

  • OP x = TP x / TP max * 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.

  • Người up: voj
  • Nguồn bài: Nguyễn Xuân Khánh