Metrô

Os sistemas de Metrô das cidades da Cosmolândia seguem sempre o mesmo padrão. Há uma estação central e uma linha circular, de modo que a estação central está dentro da área delimitada pela linha circular. A partir da estação central saem pelo menos $5$, e no máximo $100$, linhas radiais que não se interceptam entre si e que vão pelo menos até alguma estação da linha circular, podendo ir muito além, até os subúrbios mais remotos da cidade. Veja um exemplo na figura abaixo, que possui $6$ linhas radiais e onde a linha circular passa por $16$ estações.

Cada sistema possui $N$ estações, numeradas de $1$ a $N$. O número de uma estação não tem relação alguma com a sua posição no sistema. O problema é o seguinte. Um engenheiro da Agência Federal de Trânsito da Cosmolândia precisa descobrir rapidamente por quantas estações a linha circular passa. Ele tem apenas a informação sobre as ligações entre pares de estações, sem qualquer identificação das linhas às quais pertencem as duas estações do par. Você pode ajudá-lo?

Entrada

A primeira linha da entrada contém dois inteiros $N$ e $M$, respectivamente, o número total de estações e de ligações entre pares de estações. As $M$ linhas seguintes contêm, cada uma, dois inteiros $P$ e $Q$, indicando que a estação de número $P$ está ligada à estação de número $Q$.

Saída

Seu programa deve imprimir um inteiro, representando o número de estações pelas quais passa a linha circular do sistema.

Restrições

• $6 \leq N \leq 20\ 000, M \leq 20\ 100$

Exemplos

Exemplo de entrada 1

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

Exemplo de saída 1

5

Exemplo de entrada 2

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

Exemplo de saída 2

8