킹세종

세종이는 행성이 $n$개 있는 태양계의 왕이다. 행성이 너무 많아 이름을 붙이는 것은 진작 포기했고, 대신 $1$번부터 $n$번까지의 번호로 구분한다. 세종이의 집은 $1$번 행성에, PC방은 $2$번 행성에 있다.

세종이는 남들보다 빠르게 PC방에 도착해 핫타임을 놓치지 않기 위해, $1$번 행성과 $2$번 행성만을 직접 오갈 수 있는 전용 비밀 텔레포터를 가지고 있다. 이 비밀 텔레포터는 양방향이며, 한 번 이동하는 데 $250$분이 걸린다.

한편 행성들 사이에는 교통용 텔레포터가 여러 개 설치되어 있다. 각 교통 텔레포터도 양방향이며, 한 번 이동하는 데 정확히 $1$시간($60$분)이 걸린다. 시민들은 경제를 살리기 위해 교통 텔레포터를 더 많이 설치해 달라고 세종이에게 부탁했다.

세종이는 최대한 많은 부탁을 들어주고 싶지만, 단 한 가지 조건만은 지키려 한다. 교통 텔레포터만 이용해 $1$번 행성과 $2$번 행성 사이를 오가는 최소 시간이 항상 $250$분보다 커야 한다는 것이다. 즉 비밀 텔레포터가 언제나 가장 빠른 경로로 남아 있어야 한다. 교통 텔레포터 한 번이 $60$분이므로, 이는 두 행성 사이의 모든 경로가 항상 교통 텔레포터를 $5$개 이상 거쳐야 함을 뜻한다.

이 조건을 지키면서 태양계에 교통 텔레포터를 최대 몇 개까지 더 설치할 수 있는지 구하여라. 단, 이미 텔레포터로 직접 연결된 두 행성 사이에 또 다른 텔레포터를 놓는 것은 의미가 없으므로 하지 않는다. 서로 다른 한 쌍의 행성을 잇는 텔레포터는 최대 한 개이며, 한 행성에서 자기 자신으로 가는 텔레포터도 놓지 않는다.

첫째 줄에 행성의 수 $n$과 이미 설치된 교통 텔레포터의 수 $m$이 공백으로 구분되어 주어진다. ($2 \le n \le 40000$, $0 \le m \le 1000000$)

다음 $m$개의 줄에는 각 교통 텔레포터가 잇는 서로 다른 두 행성의 번호 $u$와 $v$가 주어진다. ($1 \le u, v \le n$, $u \ne v$) 여기에 세종이의 비밀 텔레포터는 포함되지 않는다. 같은 두 행성을 잇는 텔레포터가 두 번 이상 주어지지는 않는다.

이미 설치된 교통 텔레포터만으로는 어떤 경로를 이용하더라도 $1$번 행성과 $2$번 행성 사이를 $250$분 미만으로 오갈 수 없음이 보장된다. 물론 그보다 긴 시간으로는 오갈 수 있을 수 있다.

조건을 지키면서 추가로 설치할 수 있는 교통 텔레포터 개수의 최댓값을 한 줄에 출력한다.

위 그림은 한 가지 예시 상황을 나타낸다. 실선은 이미 설치된 교통 텔레포터이고, 점선은 조건을 지키면서 추가로 설치할 수 있는 교통 텔레포터를 나타낸다.