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)
Bình luận