XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: ciclovias.x, onde x deve ser c, cpp, java, js ou py

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

P1, P3, P5, … , P2x+1     e     P2, P4, P6, …, P2x
da sequência P devem ser ambas crescentes. Ganha o jogo aquele que encontrar o maior caminho. Bernardo te ligou pedindo ajuda para se preparar para o jogo. Com o mapa da cidade você deve encontrar o tamanho do maior caminho possível para todas as interseções iniciais possíveis, seguindo as restrições acima. No exemplo abaixo, o maior caminho possível para início na interseção 1 é P = (1, 3, 5, 4, 7) e para início na interseção 5 é P = (5, 3, 6) ou P = (5,4,7).

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
	

 

Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação