Description

As humanity reaches the edge of the Milky Way, it has become commonplace for ordinary people to travel to space. In a science experimental class, there are $n$ people, and the homeroom teacher wants to select as many of them as possible to go on a space trip.

However, the $n$ students do not all get along. Some people, such as Xiao A and Xiao B, are always together and are good friends; but others, such as (politically sensitive) and (politically sensitive), are incompatible. These $n$ students, being science students, are very rational, so the two statements “a friend of a friend is a friend” and “an enemy’s friend is an enemy” do not hold for them. In other words, it is possible that Xiao A and Xiao B are friends, Xiao B and Xiao C are friends, but Xiao A and Xiao C are sworn enemies.

For any two people, they are either enemies or friends. Because fights on a spaceship are very bad and dangerous, the selected students must be pairwise friends. Your task is to determine the maximum number of people who can be selected to participate.

Input Format

The first line contains an integer $n$ ($1 \le n \le 50$). All students are numbered 1 to $n$.
Then follow several lines, each containing two space-separated integers $a$, $b$ ($1 \le a, b \le n$), indicating that $a$ and $b$ are friends.
Note: If a pair $(x, y)$ (or $(y, x)$) does not appear in the file, then students $x$ and $y$ are enemies.

Output Format

A single integer, the maximum number of students that can be selected.

4
1 2
2 3
3 1
1 4

3

Hint

Translated by ChatGPT 5