$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$ тэнцэтгэл бишийг хангах ёстой гэдгийг анхаар.

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

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

% zurag

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

% zurag

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

% zurag

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

% zurag

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

% zurag

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

% zurag