34012번 - DagDag구리

문제

$N$개의 노드와 $M$개의 간선으로 이루어진 사이클이 없는 방향 그래프 $G$가 있다. $G$에는 노드 $E$가 존재하여, 모든 노드에서 $E$에 도달 가능함이 보장된다.

이 그래프에 다음 조건을 만족하도록 두 정점을 연결하는 간선을 원하는 만큼 추가하려고 한다.

• $E$가 아닌 모든 노드 $u$에 대해, $u$에서 $E$로 가는 두 개의 겹치지 않는 경로가 존재한다. 경로가 겹치지 않는다는 것은 같은 간선을 공유하지 않는다는 것을 말한다.

조건을 만족하기 위해 $G$에 추가해야 하는 간선의 최소 개수를 구해보자.

입력

첫째 줄에 노드의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다. (1ドル \le N \le 100,000円; 0\le M \le 500,000円$)

둘째 줄부터 $M$개의 줄에 걸쳐 두 정수 $u,ドル $v$가 공백으로 구분되어 주어진다. 이는 노드 $u$에서 노드 $v$로 가는 간선이 있음을 의미한다. (1ドル \le u, v \le N; u \neq v$)

동일한 노드 쌍에 여러 개의 간선이 존재할 수 있다. 주어지는 그래프에는 사이클이 없으며, 모든 노드에서 도달 가능한 노드가 존재함이 보장된다.

출력

첫째 줄에 조건을 만족하기 위해 추가해야 하는 간선의 최소 개수를 출력한다.

제한

힌트