Тоглоомын чиглэлүүд

2s

512MB

1337

0%

Graph Algorithms

Тоглоомд $m$ телепортоор холбогдсон $n$ түвшин бий; таны даалгавар бол түвшин $1$ -ээс түвшин $n$ рүү хүрэх юм. Тоглоомын суурь граф чиглэлтэй циклгүй байхаар зохиомжлогдсон. Тоглоомыг хэдэн аргаар дуусгаж болох вэ?

Эх сурвалж: cses.fi

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

Эхний мөрөнд $n$ , $m$ хоёр бүхэл тоо: түвшин болон телепортын тоо. Түвшнүүд $1,2,\dots,n$ -ээр дугаарлагдсан.

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

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

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

Хязгаарлалт

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

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