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 $P_1$, $P_2$, … , $P_K$, tal que para todo $i$, $1 \leq i < K$, existe uma ciclovia entre $P_i$ e $P_{i+1}$. Arnaldo e Bernardo estavam passeando de bicicleta 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

$$P_1, P_3, P_5, \ldots , P_{2x+1}\ \ \mbox{e}\ \ \ P_2, P_4, P_6, ..., P_{2x}$$

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 $R_1$, $R_2$, … $R_N$, onde $R_i$ é o tamanho do maior caminho possível se o jogo começar na interseção $i$.

Restrições

• $1 \leq N \leq 10^5$
• $0 \leq M \leq N(N-1)/2$
• $0 \leq M \leq 5 \times 10^5$
• $A \neq B$
• $1 \leq A, B \leq 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 \leq 7$.
• Em um conjunto de casos de teste equivalente a $40$ pontos, $N \leq 100$.
• Em um conjunto de casos de teste equivalente a $60$ pontos, $N \leq 1\ 000$.

Exemplos

Exemplo de entrada 1

5 5
1 5
1 3
1 2
2 5
4 5

Exemplo de saída 1

4 4 4 2 2

Exemplo de entrada 2

6 6
1 3
2 3
4 2
3 4
3 5
5 4

Exemplo de saída 2

7 5 6 4 2 1

Exemplo de entrada 3

7 6
1 2
1 3
3 5
3 6
5 4
4 7

Exemplo de saída 3

5 6 4 2 3 2 2