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