VM 12 Bài 02 - Đường đi dài nhất

View as PDF

Submit solution

Points: 2.00 (partial)
Time limit: 1.5s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Nguyễn Xuân Khánh
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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}, \cdots, x_{k}~ sao cho luôn có cung nối giữa đỉnh ~x_{i}~ và đỉnh ~x_{i + 1}~ ~(1 \leq 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ị ~(1 \leq N \leq 1000, 1 \leq M \leq 10000)~.
  • ~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

Output 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

Phần trăm điểm theo từng test của thí sinh (tạm gọi là ~S~) được tính theo công thức sau: gọi ~R~ là tỉ số giữa đáp án của thí sinh và đáp án của ban tổ chức,

  • Nếu ~R < 0.8~: ~S = 95^{R}(\%)~;
  • Nếu ~0.8 \leq R \leq 1~: ~S = 40 + 55^{(R - 0.8) / 0.2} (\%)~;
  • Nếu ~R > 1~: ~S = \min \left(95 + 100^{\frac{R}{3}}, 100 \right) (\%)~.

Sample Input

6 5
1 2
2 3
3 4
2 5
5 6

Sample Output

5
4 3 2 5 6

Note

Output trên sẽ được ~95\%~ điểm của test vì đường đi đã tìm được là tối ưu (và bằng với BTC)


Comments

Please read the guidelines before commenting.


There are no comments at the moment.