Estradas asfaltadas - viagem aérea

O ano não está fácil para Nlogônia. Em meio planejamento de construção das rodovias para conectar as cidades, a natureza resolveu castigar e destruiu TODAS estradas de terra deste nosso querido país.

Vimos anteriormente (no exercício anterior) que o país possui algumas componentes conexas, ou seja, núcleos de cidades conectadas entre si por estradas asfaltadas, mas sem conexão geral com as demais cidades do país. Veja abaixo a característica da cidade:

Estradas asfaltadas de Nlogônia

João é um jovem vendedor de ponteiros e está arrasado com a triste chuva que tomou conta de Nlogônia. Mais triste ainda por ter que viajar para algumas cidades. O dinheiro de João é “curto” e por isso ele tenta viajar com o bom e velho ônibus sempre que possível.

O problema é que João tem dinheiro para apenas uma passagem de avião (todos os vôos possuem o mesmo preço) e ele precisa ir para a região que possua o maior número de cidades conectadas por estrada.

João clama por ajuda!

Entrada

A entrada é composta por um único caso de teste. A primeira linha, do caso de teste, possui dois números inteiros VV (1V<50001 \leq V < 5000) e JJ (0J<V0 \leq J < V) representando, respectivamente, a quantidade de cidades existentes em Nlogônia, as cidades, para simplificar, foram nomeadas de 00 a VV, e a cidade em que João se encontra.

Depois da primeira linhas existe um conjunto indeterminado de linhas, com 00 ou mais linhas, terminando em EOF.

As demais linhas possuem dois inteiros vv e ww (0v,wV0 \leq v,w \leq V) informando a existência de uma estrada conectando as cidades vv para ww. Você pode considerar que também existe uma estrada de ww para vv. É garantido que a estrada será passada uma única vez, ou seja, se existir na entrada vwv w, não será passado wvw v.

Saída

A saída é composta por uma única linha, e dependendo do caso pode variar:

Exemplos

Exemplo de entrada

6 0
0 1
2 3
2 4
4 5

Saída para o exemplo acima

Vamos para 2

Exemplo de entrada

13 0
10 7
10 6
10 2
7 2
6 12
12 5
12 3
12 2
11 8
9 0
9 1
1 0
1 4

Saída para o exemplo acima

Vamos para 2

Exemplo de entrada

7 6
0 6
0 3
1 5
5 2

Saída para o exemplo acima

Bora pra estrada

Exemplo de entrada

6 5
0 1
2 3
2 4
4 5

Saída para o exemplo acima

Bora pra estrada

Exemplo de entrada

13 8
10 7
10 6
10 2
7 2
6 12
12 5
12 3
12 2
11 8
9 0
9 1
1 0
1 4

Saída para o exemplo acima

Vamos para 2

Exemplo de entrada

7 5
0 6
0 3
1 5
5 2

Saída para o exemplo acima

Bora pra estrada

Exemplo de entrada

13 6
10 7
10 6
10 2
7 2
6 12
12 5
12 3
12 2
11 8
9 0
9 1
1 0
1 4

Saída para o exemplo acima

Bora pra estrada

Exemplo de entrada

7 4
0 6
0 3
1 5
5 2

Saída para o exemplo acima

Vamos para 0

Exemplo de entrada

1 0

Saída para o exemplo acima

Fique em casa

Exemplo de entrada

1000 7
0 999
5 999
6 999
7 999
8 999
9 999

Saída para o exemplo acima

Bora pra estrada

Exemplo de entrada

10 0
1 9
9 8
8 7
7 6
6 5
5 4
4 3
3 2
2 1
1 0

Saída para o exemplo acima

Bora pra estrada