Ciclovias
A cidade de Nlogônia é mundialmente conhecida pelas suas iniciativas de preservação ambiental. Dentre elas, uma das que mais chama atenção é a existência de ciclovias em todas as ruas da cidade. Essa medida teve um sucesso tão grande, que agora a maioria dos moradores usa a bicicleta diariamente. Em Nlogônia, as interseções são numeradas de 1 até N. Cada rua liga duas interseções A e B e possui uma ciclovia entre A e B. Um caminho P de tamanho K é definido como uma sequência de interseções P1, P2, … , PK, tal que para todo i, 1 ≤ i < K, existe uma ciclovia entre Pi e Pi+1. Arnaldo e Bernardo estavam passeando de bicileta pelas ruas de Nlognônia quando pensaram em um novo jogo. Nesse jogo, os dois partem de alguma interseção C e procuram o caminho P de maior tamanho que satisfaça a seguinte regra: as subsequências
Entrada
A primeira linha contém dois inteiros N e M, representando respectivamente o número de interseções e o número de ruas. As M linhas seguintes contém dois inteiros A e B indicando que existe uma ciclovia entre A a B.Saída
Seu programa deve produzir uma única linha, contendo N inteiros R1, R2, … RN, onde Ri é o tamanho do maior caminho possível se o jogo começar na interseção i.Restrições
- 1 ≤ N ≤ 105
- 0 ≤ M ≤ N(N-1)/2
- 0 ≤ M ≤ 5 x 105
- A ≠ B
- 1 ≤ A, B ≤ N
- Não existem duas ciclovias iguais.
Informações sobre a pontuação
- Em um conjunto de casos de teste equivalente a 20 pontos, N ≤ 7.
- Em um conjunto de casos de teste equivalente a 40 pontos, N ≤ 100.
- Em um conjunto de casos de teste equivalente a 60 pontos, N ≤ 1000.
Exemplos
Entrada
5 5 1 5 1 3 1 2 2 5 4 5 |
Saída
4 4 4 2 2 |
Entrada
6 6 1 3 2 3 4 2 3 4 3 5 5 4 |
Saída
7 5 6 4 2 1 |
Entrada
7 6 1 2 1 3 3 5 3 6 5 4 4 7 |
Saída
5 6 4 2 3 2 2 |
