케이블 TV 네트워크

케이블 TV 네트워크에서 중계기(relay)들은 양방향 케이블로 연결됩니다. 네트워크에 존재하는 모든 중계기 쌍 사이에 적어도 하나의 연결 경로가 존재하면 그 네트워크는 연결되어 있다(connected)고 합니다. 그렇지 않으면 연결이 끊어져 있다(disconnected)고 합니다. 중계기가 하나도 없는 네트워크나 중계기가 하나뿐인 네트워크는 연결된 것으로 간주합니다.

중계기가 $n$개인 네트워크의 안전 계수(safety factor) $f$는 다음과 같이 정의됩니다.

1. 네트워크에서 몇 개의 중계기를 제거하더라도 항상 연결 상태를 유지한다면 $f = n$.
2. 그렇지 않다면, 제거했을 때 네트워크의 연결을 끊는 데 필요한 중계기의 최소 개수.

그림 1. 케이블 TV 네트워크

예를 들어 그림 1의 네트워크들을 살펴봅시다. 원은 중계기를, 실선은 연결 케이블을 나타냅니다. 네트워크 (a)는 제거하는 중계기 수와 무관하게 항상 연결되어 있으므로 규칙 (1)에 따라 $f = n = 3$입니다. 네트워크 (b)는 중계기를 하나도 제거하지 않아도 이미 연결이 끊어져 있으므로 규칙 (2)에 따라 $f = 0$입니다. 네트워크 (c)는 중계기 1과 2, 또는 1과 3을 제거하면 연결이 끊어지므로 안전 계수는 2입니다.

여러 개의 데이터 집합을 읽어, 각 데이터 집합이 나타내는 케이블 네트워크의 안전 계수를 계산하는 프로그램을 작성하세요.

각 데이터 집합은 두 정수로 시작합니다. 먼저 네트워크의 중계기 수 $n$ ($0 \le n \le 50$), 그다음 케이블 수 $m$이 주어집니다. 이어서 $m$개의 데이터 쌍 $(u, v)$가 주어지며, $u < v$이고 $u$와 $v$는 중계기 식별자($0$부터 $n-1$ 사이의 정수)입니다. 쌍 $(u, v)$는 중계기 $u$와 $v$를 잇는 케이블을 나타냅니다. 쌍들은 임의의 순서로 나타날 수 있습니다. 공백을 포함하지 않는 $(u, v)$ 쌍을 제외하면, 입력에는 공백이 자유롭게 들어갈 수 있습니다. 입력은 파일의 끝(EOF)에서 종료되며 항상 올바른 형식입니다.

각 데이터 집합에 대해, 해당 네트워크의 안전 계수를 한 줄의 시작 위치에서 표준 출력으로 출력합니다.