Представим город из n перекрестков и m улиц. Перекрестки пронумерованы от 1 до n.
Чтобы снизить количество заторов, мэр города решил сделать каждую улицу односторонней. Это значит, что на улице между перекрестками u и v машины могут ехать либо только от u до v, либо только от v до u.
Требуется так распределить направление дорожного движения на улицах, чтобы максимизировать количество пар (u, v), где 1 ≤ u, v ≤ n и можно достичь перекрёстка v, двигаясь из u, и проезжая по улицам в указанном направлении. Ваша задача — найти максимальное возможное количество таких пар.
Выходные данные
Выведите максимальное количество пар (u, v), таких, что можно достичь перекрестка v из u после распределения направления на улицах.
Примечание
В первом примере если мэр сделает первую и вторую улицу односторонними в сторону перекрестка 1, а третью и четвертую улицы — в противоположную сторону, то будет 13 пар достижимых перекрестков: {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 1), (3, 1), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
1 2
1 3
1 4
1 5
|
13
|
|
2
|
4 5
1 2
2 3
3 4
4 1
1 3
|
16
|
|
3
|
2 1
1 2
|
3
|
|
4
|
6 7
1 2
2 3
1 3
1 4
4 5
5 6
6 4
|
27
|