Description

There are $N$ rows of seats on the bus, and $2N$ people heading to the provincial contest. Each row can seat two people, and each person has two preferred rows they are willing to sit in. What is the maximum number of people who can be seated in one of their preferred rows?

Input Format

• The first line contains a positive integer $N$.
• From the second line to line $2N+1$, for $i = 1, 2, \ldots, 2N$, each line contains two positive integers $S_{i, 1}, S_{i, 2}$, representing the rows the $i$-th person wants to sit in.

Output Format

A non-negative integer, the maximum number of satisfied people.

4
1 2
1 3
1 2
1 3
1 3
2 4
1 3
2 3

7

Hint

Constraints:

• For 10% of the testdata, $N \le 10$.
• For 30% of the testdata, $N \le 50$.
• For 60% of the testdata, $N \le 200$.
• For 100% of the testdata, $N \le 2000$.

Translated by ChatGPT 5