G. Шинэ жилийн кактус

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жак, Жилл хоёр шинэ жилээр гэртээ гацуур тавихаас уйдсан тул одоо кактусыг туршиж үзэхээр болжээ. Кактус гэдэг нь энгийн, чиглэлгүй граф бөгөөд дурын хоёр цикл нь хамгийн ихдээ нэг ерөнхий оройтой байдаг. Өөрөөр хэлвэл нэг ирмэгийг өөртөө агуулсан $2$ цикл байхгүй гэсэн үг.

$12$-р сарын $31$-нд тэр хоёр кактусдаа тоглоом өлгөж чимэглэхээр шийдсэн. Нэг орой дээр хамгийн ихдээ нэг тоглоом өлгөж болох бөгөөд Жак, Жилл хоёр ээлжилж тоглоомнуудыг өлгөнө. Зарим орой тоглоомгүй үлдэж болно.

Жак, Жилл хоёр муудалчихсан байгаа тул нэг оройд нь Жакын, нөгөө оройд нь Жиллийн өлгөсөн тоглоом байх ирмэг байлгахыг хүсэхгүй байгаа.

Жак нийт $a$ тоглоом өлгөнө. Хэрвээ Жак, Жилл хоёр хоёул хамгийн сайн тактикаар тоглож Жиллийн өлгөх боломжит $b$ тоглоомын тоог хамгийн их байлгахыг хүсэж байгаа. Ийм бол $a$ нь $0$-с графын нийт оройн тоо хүртлэх бүх утганд $b$-н утгыг олно уу.

Оролт

Эхний мөрөнд оройн тоог илэрхийлэх $n$, ирмэгийн тоог илэрхийлэх $m$ ($1 ≤ n ≤ 2500$, $n-1 ≤ m$) байна. Дараагийн $m$ мөр бүрт холбогдосн хоёр ирмэгийн дугаар болох $a$, $b$ ($1 ≤ a, b ≤ n$, $a ≠ b$) өгөгдөнө. Аль ч хоёр хос оройн хооронд хамгийн ихдээ нэг ирмэг оршино.

Гаралт

Нэг мөрөнд Жакын өлгөх тоглоомын тоо $a$-н бүх утганд Жиллийн өлгөх тоглоомын тоо $b$-н боломжит хамгийн их утгуудыг хэвлэнэ. $b_a$ тоонууд нь $a$-н өсөх эрэмбээр эрэмблэгдсэн байна.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
1 0
Гаралт
1 0 
Оролт
16 20
1 2
3 4
5 6
6 7
7 8
9 10
10 11
11 12
13 14
15 16
1 5
9 13
14 10
10 6
6 2
15 11
11 7
7 3
16 12
8 4
Гаралт
16 13 12 12 10 8 8 7 6 4 4 3 3 1 0 0 0 

Тэмдэглэл

The cactus from the second example is:

Сэтгэгдлүүдийг ачааллаж байна...