트리 재구성

방향 그래프가 하나 있고, 각 간선에는 0 이상의 값이 하나씩 적혀 있다. 이 값들은 흐름 보존 법칙을 만족한다. 즉 모든 정점 $v$에 대해 $v$로 들어오는 간선의 값의 합과 $v$에서 나가는 간선의 값의 합이 같다.

간선의 부분집합 $E'$를 하나 고른 뒤, $E'$에 속하지 않는 간선의 값을 모두 지운다. 이제 남은 정보만 보고 지운 값을 되살리려고 한다. 흐름 보존 법칙 덕분에 지운 값이 전부 되살아나는 경우도 있다. $E'$에 적힌 값이 무엇이든 흐름 보존 법칙만으로 나머지 간선의 값이 유일하게 정해질 때, $E'$를 복원 가능한 집합이라고 하자.

복원 가능한 $E'$ 중에서 크기가 가장 작은 것의 크기를 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 형식은 다음과 같다.

N M
s1 t1
...
sM tM

첫 줄에 정점의 개수 $N$ ($1 \le N \le 500$)과 간선의 개수 $M$ ($0 \le M \le 3000$)이 주어진다. 이어지는 $M$개의 줄에는 정수 $s_i$와 $t_i$ ($1 \le s_i, t_i \le N$)가 주어지고, 이는 $s_i$에서 $t_i$로 가는 간선이 있다는 뜻이다.

주어지는 그래프는 단순하다.

• 자기 자신으로 가는 간선은 없다. 즉 $s_i \ne t_i$다.
• 방향까지 같은 간선이 두 번 주어지지는 않는다. 즉 $i < j$이면 $(s_i, t_i) \ne (s_j, t_j)$다.

또 그래프의 각 연결 요소는 강한 연결 요소다. 즉 정점 $v$에서 $u$로 가는 경로가 있으면 $u$에서 $v$로 가는 경로도 있다.

간선에 적힌 값은 답을 바꾸지 않으므로 입력에 주어지지 않는다.

입력은 파일이 끝날 때까지 이어진다.

각 테스트 케이스마다 답을 한 줄에 출력한다.