Domino Line

Time limit1sMemory limit512 MB

Summary

Each domino is an edge between two values; partition all edges into the fewest trails, which by Euler path counting depends on odd-degree vertices per component.

Level: Medium6 of 10
Topics: Graph, Union-find, Greedy, Implementation
Solved: No attempts yet

Problem

A domino piece is a rectangular tile whose face is divided by a line into two square halves. Each half contains a number of dots representing the value of that half. A domino is named by the values of its two halves (also called its ends); for example, a domino with 2 dots in one half and 5 dots in the other is a 2-5 (or 5-2) domino.

Dominoes is played by laying down dominoes one by one, next to each other, so that touching ends have the same value. A domino line is a sequence of dominoes in which each pair of adjacent dominoes has the same value on their touching ends, that is, a validly played sequence of dominoes. For example, the sequence (2-5, 5-4, 4-4, 4-6, 6-3) is a valid domino line, while (2-5, 5-3, 5-4, 4-6) is not, because 5-3 and 5-4 do not share the same value on their touching ends (3 and 5). A domino piece can be played in either direction; for example, a 3-5 domino can be played as 5-3.

Given a set of N dominoes, lay down all of them so that the number of domino lines is as small as possible.

For example, suppose there are 6 dominoes: {2-6, 1-3, 4-2, 6-3, 2-5, 4-3}. For readability, denote them as D1, D2, D3, D4, D5, and D6, respectively. If a domino D1 is played in reversed order (playing 6-2 with a 2-6 domino), we call it R1, and likewise for the other dominoes.

The minimum number of domino lines needed is 2:

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

There are other ways to lay down the dominoes, but none forms fewer than 2 domino lines in this example.

Find the minimum number of domino lines that can be formed with the given set of dominoes.

Input

The first line contains an integer N (1 ≤ N ≤ 50,000), the number of dominoes. The next N lines each contain two integers A B (1 ≤ A, B ≤ 50,000), representing an A-B domino.

Output

Output in a single line the minimum number of domino lines that have to be formed to lay down all the given dominoes.

Examples3

Example 1
Input
```
4
2 6
1 3
6 3
2 5
```
Expected output
```
1
```
Example 2
Input
```
4
1 2
1 2
4 5
3 6
```
Expected output
```
3
```
Example 3
Input
```
7
1 3
4 8
7 3
6 4
5 7
3 6
2 5
```
Expected output
```
2
```