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