B. Дзи химид дуртай

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

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

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

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

Дзи химид дуртай бөгөөд тэр химийн бодисуудыг холих дуртай.

Дзид $n$ химийн бодис байгаа бөгөөд тэднээс $m$ нь хос хосоороо урвалд ордог. Тэр химийн бодисуудыг дурын дарааллаар туршилтын хоолой руу нэг нэгээр нь хийж холих гэж байна.

Туршилтын хоолойн эрсдлийг авч үзье. Хоосон туршилтын хоолойн эрсдэл $1$ байна. Дзиг бодис нэмэх бүрд хэрвээ хоолойд энэ бодистой урвалд ордог бодис байвал хоолойн эрсдлийг 2-р үржүүлнэ. Эсрэг тохиолдолд эрсдэл нь хэвээрээ байна.

Бүх химийн бодисуудыг ямар нэг дарааллаар туршилтын хоолой руу нэг нэгээр нь хийсний дараах хамгийн их эрсдлийг ол.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан $n$, $m$ ($1 ≤ n ≤ 50; 0 ≤ m ≤ \frac{n(n-1)}{2}$) бүхэл тоонуудыг агуулна.

Дараагийн $m$ мөр бүр нь зайгаар тусгаарлагдсан $x_{i}$, $y_{i}$ $(1 ≤ x_{i} < y_{i} ≤ n)$ бүхэл тоонуудыг агуулна. Эдгээр бүхэл тоонууд нь $x_{i}$ химийн бодисыг $y_{i}$ химийн бодистой урвалд оруулж болохыг илэрхийлнэ. Химийн бодисын хос бүр хамгийн ихдээ нэг удаа оролтонд гарч ирж болно.

Бодисуудыг $1$-с $n$ хүртэл дугаарлагдсан гэж үзнэ.

Гаралт

Боломжит хамгийн их эрсдэл болох нэг бүхэл тоо хэвлэнэ.

Орчуулсан: Даариймаа

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

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

Тэмдэглэл

Эхний жишээнд зөвхөн нэг аргаар холих ба эрсдэл өсөхгүй.

Хоёр дахь жишээнд, бид эхлээд $1$-р химийн бодисыг хийх, эсвэл $2$-р химийн бодисыг хийсэн ч хариулт ялгаагүй $2$ байна.

Гурав дахь жишээнд, хамгийн их эрсдэлд хүрэх дөрвөн арга байгаа: 2-1-3, 2-3-1, 1-2-3 ба 3-2-1 (химийн бодисуудыг холих дарааллын тоо).

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