Vòng quanh thế giới

Cho một đất nước gồm $n$ thành phố và $m$ con đường một chiều. Tất cả các con đường đều có cùng độ dài bằng $1$.

Bạn cần chọn ra bốn thành phố khác nhau và sắp xếp chúng theo một thứ tự thăm $v_1,v_2,v_3,v_4$. Người du khách sẽ lần lượt đi từ $v_1$ đến $v_2$, từ $v_2$ đến $v_3$, rồi từ $v_3$ đến $v_4$, mỗi chặng luôn đi theo đường ngắn nhất giữa hai thành phố tương ứng. Trên mỗi chặng, đường đi có thể đi qua các thành phố khác (kể cả các thành phố nằm trong hành trình) và có thể đi qua cùng một thành phố nhiều lần.

Gọi $d(x,y)$ là độ dài đường đi ngắn nhất (số cạnh) từ $x$ đến $y$. Hãy chọn thứ tự thăm sao cho tổng quãng đường

$$d(v_1,v_2)+d(v_2,v_3)+d(v_3,v_4)$$

là lớn nhất có thể.

Dữ liệu đảm bảo luôn tồn tại cách chọn bốn thành phố khác nhau sao cho cả ba chặng đều đi được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số thành phố và số con đường một chiều.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i,v_i$ — một con đường một chiều từ $u_i$ đến $v_i$. Các đỉnh $u_i,v_i$ không nhất thiết phân biệt và có thể có nhiều con đường giữa cùng một cặp thành phố.

Dữ liệu ra

In ra bốn số nguyên là số hiệu của bốn thành phố theo đúng thứ tự thăm sao cho tổng quãng đường là lớn nhất. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $4\le n\le 3000$
• $3\le m\le 5000$
• $1\le u_i,v_i\le n$

Ví dụ