reunai   1년 전

# 문제 

이미 지난해, UOB(바이토치아 보호국)은 바이토치아 인터넷 회선을 겨냥한 계획된 테러에 대해 알게 되었다. 오랜 수사 끝에 이 공격의 배후에는 단 한 사람이 있다는 사실이 밝혀졌다. 전체 작전의 두뇌는 아마도 "S**"라는 가명을 쓰는 어떤 정보학자일 것이다(수사의 이익을 위해 그의 정체를 완전히 공개할 수는 없다). 그러나 몇 달 동안 대대적인 수색에도 불구하고 그는 발견되지 않고 있다.

수사 과정에서 입수한 정보에 따르면 공격의 목표는 서버 1에서 서버 n으로 메시지를 전송하는 것을 불가능하게 만드는 것이다.

바이토치아 인터넷은 우리가 아는 인터넷과 크게 다르지 않다. 서버들과 그 사이의 인터넷 연결로 구성되어 있다. 그러나 바이토치아의 회선은 단방향이다. 교활한 정보학자 "S**"는 연결들에 덫을 설치해 두었다. 덫이 발동되면 설치된 연결이 끊어지게 된다.

알려진 바로는 "S**"가 가능한 최소한의 수의 덫만을 설치했지만, 그럼에도 불구하고 서버 1에서 서버 n으로의 통신이 불가능해지도록 만들었다고 한다.

UOB는 최고의 프로그래머인 당신에게 도움을 요청하고 있다. 그들이 알고 싶은 것은, "S가 몇 개의 덫을 설치하도록 지시했는가"이다(그 덫들을 실제로 어떻게 찾을지는 또 다른 문제다).

# 입력

입력으로는 바이토치아 인터넷망에 대한 정보가 주어진다.
첫 번째 줄에는 두 정수 n과 m이 주어지며 (2 ≤ n ≤ 10 000), 각각 서버의 개수와 연결(링크)의 개수를 의미한다. 서버들은 1번부터 n번까지 번호가 매겨져 있다.

다음 m개의 줄에는 각 연결의 설명이 주어진다. 각 연결은 두 정수 a와 b로 표현되며 (1 ≤ a, b ≤ n, a ≠ b), 이는 서버 a에서 서버 b로 가는 단방향 연결이 존재한다는 의미이다.

또한, 두 서버 사이에는 최대 하나의 직접 연결만 존재한다는 것이 보장된다.

# 출력 
출력에는 하나의 정수가 주어진다 — 서버 1과 서버 n 사이의 연결을 끊기 위해 "S**"가 설치하도록 지시한 최소한의 덫의 개수.

댓글을 작성하려면 로그인해야 합니다.