맥주 범람 시스템

트리케라톱스 양조장은 복잡한 자동 파이프 시스템으로 여러 지역 펍, 식당 및 기타 장소에 맥주를 공급한다. 이 시스템을 맥주 범람 시스템이라고 부른다. 최근 양조장은 대대적인 개편을 계획하고 있다.

시스템은 하나의 공급 스테이션, 하나의 수집 스테이션, 여러 펌핑 스테이션, 그리고 파이프로 구성된다. 공급 스테이션은 양조장에 있다. 모든 펌핑 스테이션은 펍, 식당 등에 있다. 수집 스테이션의 위치는 다소 불명확하지만 시스템 기능에는 중요하지 않다.

파이프는 여러 스테이션을 연결한다. 공급 스테이션은 적어도 하나의 다른 스테이션과 연결되며, 수집 스테이션도 적어도 하나의 다른 스테이션과 연결된다. 수집 스테이션이 공급 스테이션과 동일한 극단적인 경우에는 펌핑 스테이션도 파이프도 없다.

맥주는 공급 스테이션에서 파이프를 통해 다른 스테이션으로 흐르며, 그곳에서 일부가 소비될 수 있다(그리고 종종 소비된다). 펌핑 스테이션에서 소비되지 않은 나머지 맥주는 자동으로 파이프를 통해 다른 펌핑 스테이션 또는 수집 스테이션으로 계속 흐른다.

시스템 내 맥주 흐름의 방향은 스테이션을 떠난 맥주가 다시 같은 스테이션으로 돌아올 수 없도록 정해져 있다. 어떤 스테이션 부분집합을 통해서도 순환 흐름이 생기지 않는다. 또한 연결된 두 스테이션 사이의 맥주 흐름 방향은 고정되어 있으며 시간이 지나도 변하지 않는다. 공급 스테이션에서 시스템을 통해 흐르는 맥주 양은 모든 펌핑 스테이션을 공급하기에 충분하다. 시스템의 모든 파이프에는 항상 어느 정도의 맥주가 흐른다.

현재의 맥주 범람 시스템은 컴퓨터 기반 최적화가 미래의 꿈이었던 오래전에 지어졌다. 나중에 신중하게 선택한 일부 중복 파이프를 제거하고 나머지 파이프의 맥주 흐름을 조정하여 시스템의 주요 특징을 유지할 수 있을 가능성이 매우 높다는 것이 밝혀졌다. 특히 모든 펌핑 스테이션은 여전히 공급 스테이션으로부터 충분한 맥주를 받고, 펌핑 스테이션에서 소비되지 않은 모든 맥주는 여전히 수집 스테이션에 도달한다. 또한 시스템의 모든 파이프에 다시 어느 정도의 맥주가 흐르고, 남은 파이프의 맥주 흐름 방향은 변하지 않는다. 모든 파이프의 용량이 매우 커서 일부 파이프의 맥주 흐름이 증가하더라도 남은 파이프를 확장할 필요가 없다.

맥주 범람 시스템의 위상이 주어졌을 때, 시스템에서 제거할 수 있는 파이프의 최대 개수를 계산하라.

첫 번째 줄에는 두 정수 N, M이 주어진다. (1 ≤ N ≤ 2000, 0 ≤ M ≤ 5000) N은 공급 스테이션과 수집 스테이션을 포함한 맥주 범람 시스템의 모든 스테이션 수이다. M은 시스템의 파이프 수이다. 스테이션은 정수 1, 2, . . . , N으로 표시된다. 다음 M개의 줄에는 각각 하나의 파이프와 그 파이프를 통과하는 맥주 흐름의 방향이 주어진다. 각 줄에는 두 정수 X와 Y가 주어진다. (1 ≤ X, Y ≤ N; X ≠ Y) 맥주는 스테이션 X에서 스테이션 Y로 흐른다. 모든 파이프는 서로 다른 두 스테이션을 연결하며, 자기 자신을 연결하는 파이프는 없다. 입력에서 들어오는 흐름이 없는 스테이션은 정확히 하나이며, 그것이 공급 스테이션이다. 또한 다른 어떤 스테이션으로도 맥주가 흐르지 않는 스테이션도 정확히 하나이며, 그것이 수집 스테이션이다.

맥주 범람 시스템에서 제거할 수 있는 파이프의 최대 개수를 하나의 정수로 출력한다.