전력망

한 회사가 여러 발전소를 통해 전기를 공급하며, 각 발전소는 자신을 둘러싼 작은 지역에 전력을 보낸다. 어떤 지역은 전력이 부족한데 다른 지역은 크게 남는 상황이 자주 생기므로, 회사는 일부 발전소의 네트워크를 서로 연결하기로 했다.

적어도 초기 단계에서는 모든 발전소를 하나의 네트워크로 묶을 필요는 없다. 반면 중요한 지점에는 중복 연결을 만들어 두는 편이 이득일 수 있으므로, 합쳐진 네트워크에는 사이클이 존재할 수도 있다.

설계안을 평가하는 기준 중 하나는 신뢰성이다. 최악의 상황은 발전소에 있는 연결 지점 하나가 고장 나 네트워크가 여러 조각으로 분리되는 경우라고 가정한다. 각 조각은 따로따로 계속 작동할 수 있지만, 저마다 부족분을 스스로 감당해야 하므로 연결 지점 하나의 고장이 네트워크를 최대 몇 조각으로 쪼갤 수 있는지 아는 것이 중요하다.

네트워크에 대한 설명이 주어질 때, 연결 지점 하나를 제거했을 때 네트워크가 분리될 수 있는 조각의 최대 개수를 구하는 프로그램을 작성하라. 이때 제거된 연결 지점 자신은 개수에 포함하지 않는다.

입력은 여러 개의 인스턴스로 이루어진다.

각 인스턴스의 첫 줄에는 공백으로 구분된 두 정수 $P$와 $C$가 주어진다. 여기서 $1 \le P \le 10000$이고 $C \ge 0$이다. $P$는 발전소의 수이고, 발전소에는 $0$부터 $P-1$까지의 번호가 매겨져 있다. $C$는 연결의 수이다.

이어지는 $C$개의 줄에는 각각 두 정수 $p_1$과 $p_2$($0 \le p_1, p_2 < P$)가 주어지며, 이는 발전소 $p_1$과 $p_2$가 연결되어 있음을 뜻한다. 모든 연결은 정확히 한 번씩만 주어지고, 임의의 두 발전소 사이에는 연결이 최대 한 개뿐이다.

인스턴스는 구분자 없이 바로 이어진다. 입력은 두 개의 $0$이 적힌 줄로 끝난다.

각 인스턴스마다 한 줄에 정수 하나를 출력한다. 이 값은 발전소의 연결 지점 하나를 제거하여 얻을 수 있는, 서로 분리된 네트워크 조각의 최대 개수이다.