Avançado Informática - Semana 33

Maior Menor Caminho

Dado um grafo direcionado e sem pesos de $N$ vértices, numerados de $1$ a $n$ , seja $d(A,B)$ a menor distância entre os vértices $A$ e $B$ . Sua tarefa é escolher quatro vértices distintos $A$ , $B$ , $C$ e $D$ de modo a maximizar a soma $d(A,B)+d(B,C)+d(C,D)$ .

Entrada

A primeira linha da entrada contêm $2$ inteiros: $N$ e $M$ , o número de vértices e o número de arestas do grafo, respectivamente.

Cada linha $i$ das próximas $m$ linhas irá conter $2$ inteiros $V_i$ e $U_i$ , respectivamente, indicando que há uma aresta que sai de $V_i$ e chega em $U_i$ .

Saída

Sua saída deve conter uma única linha com quatro inteiros: os valores de $A$ , $B$ , $C$ e $D$ , respectivamente. Se há mais de uma possível solução, imprima qualquer uma delas.

Limites

$4 \leq N \leq 3000$
$3 \leq M \leq 5000$
$1 \leq V_i, U_i \leq n$

Exemplo

Entrada

Saída

8 9

1 2

2 3

3 4

4 1

4 5

5 6

6 7

7 8

8 5

2 1 8 7