| Codeforces Round 338 (Div. 2) |
|---|
| Закончено |
Под новый год Дед Мороз подарил Маше волшебную картинку и карандаш. Картинка состоит из n точек, соединённых m отрезками (отрезки могут пересекаться как угодно, это неважно). Никакие два отрезка не соединяют одну и ту же пару точек, никакой отрезок не соединяет точку саму с собой. Маша хочет нарисовать ежа, но чтобы он ожил в новогоднюю ночь, нужно, чтобы у него был раскрашенный хвост, соответствующий нескольким правилам:
- Раскрашивать можно только те отрезки, которые уже были на картинке;
- Хвост должен быть непрерывным, то есть состоять из последовательности точек, такой что все пары соседних точек соединены раскрашенным отрезком;
- Номера точек от начала хвоста к его концу должны строго возрастать.
Назовём длиной хвоста количество точек в нём. Помимо хвоста, Маша собирается нарисовать ежу колючки, для этого она раскрасит все отрезки, одним из концов которых является последняя точка хвоста (точка хвоста с максимальным номером). Красотой ежа Маша называет количество колючек, умноженное на длину хвоста. Маша хочет нарисовать самого красивого ежа. Помогите ей посчитать, на что она может рассчитывать.
Обратите внимание, что, согласно Машиному определению ежа, один и тот же раскрашенный отрезок может быть одновременно и колючкой, и частью хвоста (всё-таки Маша ещё маленькая девочка). Для уточнения посмотрите на картинку к первому примеру.
В первой строке входных данных записаны два числа n и m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000) — количество точек и отрезков на подаренной Маше картинке соответственно.
В следующих m строках содержится по два числа ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — номера точек, которые соединяет данный отрезок. Гарантируется, что никакие два отрезка не соединяют одну и ту же пару точек.
Выведите максимально возможную красоту ежа.
8 6
4 5
3 5
2 5
1 2
2 8
6 7
9
4 6
1 2
1 3
1 4
2 3
2 4
3 4
12
На рисунке изображён первый пример. Красным обозначены отрезки, составляющие ежа. Хвост состоит из последовательности точек 1, 2 и 5. Колючками являются отрезки между парами точек (2, 5), (3, 5) и (4, 5). Таким образом, красота ежа равняется 3·3 = 9. 
