도미노 줄

도미노 조각은 직사각형 모양의 타일로, 겉면이 선 하나로 두 개의 정사각형 칸으로 나뉘어 있다. 각 칸에는 그 칸의 값을 나타내는 점이 여러 개 찍혀 있다. 도미노는 두 칸의 값(양 끝 값)으로 부르며, 예를 들어 한쪽에 점이 2개, 다른 쪽에 5개 있으면 2-5(또는 5-2) 도미노라고 한다.

도미노 게임은 도미노를 하나씩 옆으로 이어 붙이되, 맞닿은 끝의 값이 같도록 놓는 방식으로 진행한다. 도미노 줄이란 인접한 두 도미노의 맞닿은 끝 값이 같은 도미노의 나열, 즉 규칙에 맞게 놓인 도미노의 나열이다. 예를 들어 (2-5, 5-4, 4-4, 4-6, 6-3)은 올바른 도미노 줄이고, (2-5, 5-3, 5-4, 4-6)은 5-3과 5-4의 맞닿은 끝 값(3과 5)이 다르므로 올바르지 않다. 도미노 조각은 어느 방향으로든 놓을 수 있다. 예를 들어 3-5 도미노는 5-3으로 놓을 수 있다.

N개의 도미노가 주어질 때, 모든 도미노를 놓으면서 도미노 줄의 개수가 최소가 되도록 하려 한다.

예를 들어 6개의 도미노 {2-6, 1-3, 4-2, 6-3, 2-5, 4-3}이 있다고 하자. 읽기 쉽도록 각각을 D1, D2, D3, D4, D5, D6이라 하자. 도미노 D1을 뒤집어서 놓으면(2-6 도미노를 6-2로 놓는 경우), 이를 R1이라 하고 나머지 도미노도 마찬가지로 표기한다.

필요한 도미노 줄의 최소 개수는 2이다.

• D2, R4, R1, D5: 1-3, 3-6, 6-2, 2-5.
• R3, D6: 2-4, 4-3.

다른 방법으로도 도미노를 놓을 수 있지만, 이 예에서 도미노 줄을 2개보다 적게 만드는 방법은 없다.

주어진 도미노 집합으로 만들 수 있는 도미노 줄의 최소 개수를 구하시오.

첫째 줄에는 도미노의 개수 N (1 ≤ N ≤ 50,000)이 주어진다. 다음 N개 줄에는 각각 두 정수 A B (1 ≤ A, B ≤ 50,000)가 주어지며, A-B 도미노를 나타낸다.

주어진 도미노를 모두 놓기 위해 만들어야 하는 도미노 줄의 최소 개수를 한 줄에 출력한다.