В честь проведения второго турнира ABBYY Cup Умный Бобер решил устроить вечеринку. У Бобра много знакомых, и некоторые из них дружат друг с другом, а некоторые друг другу не нравятся. Чтобы вечеринка удалась на славу, Умный Бобер хочет пригласить только тех своих знакомых, которые дружат, и не приглашать тех, кто не нравится друг другу. Отношения дружбы и антипатии симметричны.
Более формально, для каждого приглашенного человека должны выполняться следующие условия:
- все его друзья должны быть также приглашены на вечеринку;
- среди приглашенных не должно быть людей, которые ему не нравятся;
- все приглашенные на вечеринку должны быть связаны с ним дружбой напрямую или через цепь общих друзей произвольной длины. Будем говорить, что люди a1 и ap связаны цепью общих друзей, если существует последовательность людей a2, a3, ..., ap - 1 такая, что все пары людей ai и ai + 1 (1 ≤ i < p) — друзья.
Помогите Бобру определить максимальное количество знакомых, которых он сможет пригласить.
Выходные данные
Выведите единственное число — максимальное количество людей, которых Бобер сможет пригласить на вечеринку. Если группу людей, удовлетворяющую всем требованиям, выбрать невозможно, выведите 0.
Примечание
Рассмотрим пример.
Под условия задачи подходят две группы людей: {1, 2, 3} и {4, 5}, при этом ответом будет размер наибольшей из этих групп. Группа {6, 7, 8, 9} не подходит, так как в ней есть люди 7 и 9, которые не нравятся друг другу. Группа {1, 2, 3, 4, 5} также не подходит, так как не все ее члены связаны цепью общих друзей (например, люди 2 и 5 не связаны).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
8
1 2
1 3
2 3
4 5
6 7
7 8
8 9
9 6
2
1 6
7 9
|
3
|