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

Дзид $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$-р химийн бодисыг хийх, эсвэл $2$-р химийн бодисыг хийсэн ч хариулт ялгаагүй $2$ байна.

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