C. Цикллэг будалт

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

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

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

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

$n$ оройтой, $m$ ирмэгтэй $G$ чиглэлт граф (давхар ирмэг, өрлүүгээ орсон ирмэг байгаа) өгөгдсөн. Та графын орой бүрийг $k (k <= n)$ будгийн нэгээр будах ёстой ба будахдаа $u$ оройгоос $v$ орой хүрэх бүх ирмэгийн хувьд $u$ оройг будсан өнгийн дараагийн өнгөөр $v$ оройг будна.

Өнгүүд 1-ээс $k$-руу цикл байдлаар дугаарлагдана. Энэ нь $i (i < k)$ өнгө бүрийн хувьд дараагийн өнгө $i + 1$ гэсэн үг. Мөн $k$ өнгийн дараагийн өнгө нь 1. Хэрэв $k = 1$ бол 1 өнгийн дараагийн өнгө ахиад л 1 болохыг анхаар.

Таны даалгавар бол $G$ графыг $k$ өнгөөр дээрх дүрсэлсэн байдлаар будахад $k (k <= n)$-ийн хамгийн том утгыг олж хэвлэх. Та бүх $k$ өнгийг хэрэглэх албагүйг анхаар (энэ нь $i$ өнгө бүрийн хувьд $i$ өнгөөр будагдсан орой байх албагүй).

Оролт

Эхний мөр харгалзан оройнуудын тоо, өгөгдсөн чиглэлт графын ирмэгүүдийн тоо болох зайгаар тусгаарлагдсан $n, m (1 <= n, m <= 10^5)$ бүхэл тоог агуулна.

Дараагаар нь $m$ мөр дагалдах ба мөр бүр $a_i$ оройгоос $b_i$ оройд хүрч байгаа $i$ ирмэгийн $a_i, b_i (1 <= a_i, b_i <= n)$ хоосон зайгаар тусгаарлагдсан хоёр бүхэл тоог агуулна.

Давхар ирмэг, өөрлүүгээ орсон ирмэг байгаа.

Гаралт

Чиглэлт графыг будахад хэрэглэгдэх хамгийн их өнгийн тоо ганц бүхэл тоог (энд бодлогод дүрлэгдсэн $k$) хэвлэнэ. $k$-ийн утга $1 <= k <= n$ тэнцэтгэл бишийг хангах ёстой гэдгийг анхаар.

Орчуулсан: devman

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

Оролт
4 4
1 2
2 1
3 4
4 3
Гаралт
2
Оролт
5 2
1 4
2 5
Гаралт
5
Оролт
4 5
1 2
2 3
3 1
2 4
4 1
Гаралт
3
Оролт
4 4
1 1
1 2
2 1
1 2
Гаралт
1

Тэмдэглэл

Хамгийн эхний жишээнд k = 2 байхад доорх зураг 2 өнгөтэйгөөр зурагдсан (сумууд нь тэр өнгийн дараагийн өнгийг дүрслэнэ).

$k = 2$ байхад графыг будах боломжит арга нь доорх.

% zurag

Энэ жишээнд $k$-ийг өөр том утга байхгүй гэдгийг баталж болно.

% zurag

Хоёр дугаар жишээнд $k = 5$ байх зургийг харуулав.

% zurag

Графыг будах боломжит будалтууд:

% zurag

Гурав дугаар жишээнд $k = 3$ өнгүүд байх зураг.

% zurag

Графыг будах нэг боломжит арга:

% zurag

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