Eight 2 Zero

네트워크 시스템은 노드와 링크로 구성된다. 링크는 서로 다른 두 노드를 양방향으로 연결한다. 링크로 직접 연결된 두 노드는 통신할 수 있으며, $A$와 $B$가 통신할 수 있고 $B$와 $C$가 통신할 수 있으면 $A$와 $C$도 통신할 수 있다.

$1$번부터 $N$번까지 번호가 매겨진 $N$개의 노드와 $N+1$개의 링크로 이루어진 네트워크가 있다. 임의의 두 노드를 연결하는 링크는 최대 하나이고, 임의의 노드 간에 통신할 수 있는 네트워크이다.

네트워크가 너무 복잡하다고 생각한 당신은 일부 링크를 제거하기로 했다. 링크를 제거하다 보면 다른 어떤 노드와도 통신할 수 없는 노드가 생길 수 있다. 이런 노드를 비활성 노드라고 하고, 비활성 노드가 아닌 노드를 활성 노드라고 하자.

당신은 링(Ring)이 가장 단순한 구조라고 보고, 링으로만 이루어진 네트워크를 만들려고 한다. 임의의 노드 간에 통신할 수 있고, 임의의 노드에서 출발해 링크를 따라 통신을 반복하면 시작 노드로 돌아올 수 있는 부분 네트워크를 링이라고 한다. 이때 하나 이상의 링크를 사용해야 하며, 같은 링크를 두 번 이상 사용하면 안 된다. 링의 예시는 다음과 같다.

다음은 링이 아닌 네트워크의 예시이다. 링을 포함하는 네트워크는 있지만, 전체 네트워크 기준으로는 링이 아니므로 주의하자.

모든 활성 노드가 정확히 하나의 링에 속하도록 하기 위해 제거해야 하는 링크 개수의 최솟값을 구하시오.

첫째 줄에 노드의 개수 $N$이 주어진다. $(4\leq N \leq 300\,000)$

둘째 줄부터 $N+1$개의 줄에 걸쳐 링크의 정보가 주어진다. 각 줄에는 그 링크가 연결하는 두 노드의 번호가 공백으로 구분되어 주어진다.

첫째 줄에 제거해야 하는 링크 개수의 최솟값을 출력한다.