Гамильтонов нислэгүүд

2s

512MB

1457

0%

Graph Algorithms

$n$ хот, тэдгээрийн хооронд $m$ нислэгийн холболт бий. Сюрьялягаас Лехмяля руу хот бүрд яг нэг удаа орж очихыг хүсдэг. Хэдэн боломжит чиглэл байна вэ?

https://cses.fi/problemset/task/1690

Оролтын формат

Эхний мөрөнд $n$ , $m$ хоёр бүхэл тоо: хот болон нислэгийн тоо. Хотууд $1,2,\dots,n$ -ээр дугаарлагдсан. $1$ дугаар хот Сюрьяля, $n$ дугаар хот Лехмяля.

Дараа нь $m$ мөрөнд нислэгүүд байна. Мөр бүрд $a$ , $b$ хоёр бүхэл тоо: $a$ хотоос $b$ хот руу нислэг бий. Нислэг бүр нэг чиглэлтэй.

Гаралтын формат

Нэг бүхэл тоо хэвлэ: чиглэлүүдийн тооны $10^9+7$ -д хуваасан үлдэгдэл.

Хязгаарлалт

$2 \le n \le 20$
$1 \le m \le n^2$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...