E. Кактус

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

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

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

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

Хэрвээ графын орой бүр нь хамгийн ихдээ нэг циклд хамаарагдаж байвал уг холбогдсон чиглэлгүй графыг оройн кактус гэнэ.

Чиглэлгүй граф дахь энгийн цикл нь дурын $i$-н $(1 ≤ i < t)$ хувьд $v_{i}$ ба $v_{i + 1}$ оройнуудын хооронд болон $v_{1}$ ба $v_{t}$ оройнуудын хооронд ирмэг оршин байх ялгаатай $v_{1}, v_{2}, ..., v_{t}$ $(t > 2)$ оройнуудын дараалал юм.

Чиглэлгүй граф дахь энгийн зам нь дурын $i$-н $(1 ≤ i < t)$ хувьд $v_{i}$ ба $v_{i + 1}$ оройнуудын хооронд ирмэг оршин байх ба түүнчлэн ирмэг бүр нэгээс олон тохиолдохгүй, ялгаатай байх албагүй $v_{1}, v_{2}, ..., v_{t}$ $(t > 0)$ оройнуудын дараалал байна. Бид $v_{1}, v_{2}, ..., v_{t}$ энгийн замыг $v_{1}$ оройгоос эхэлж $v_{t}$ дуусч байна гэж хэлнэ.

Танд $n$ орой болон $m$ ирмэгээс бүрдэх граф буюу оройн кактус байна. Мөн танд мэдээллийг нь сонирхож буй $k$ ширхэг $x_{i}, y_{i}$ хос оройн жагсаалт байна. Мэдэхийг хүсч буй мэдээлэл нь $x_{i}$ оройгоос эхлээд $y_{i}$ оройд дуусах ялгаатай энгийн замуудын тоо юм. Хэрвээ замуудын ирмэгүүдийн бүрдэл нь ялгаатай байвал замууд ялгаатайд тооцогдоно.

Сонирхож буй хос орой бүрийн хувьд тэдгээрийн хоорондох ялгаатай энгийн замуудын тоог тоол. Уг тоо нь маш их байж болох учир та хариуг $1000000007$ ($10^{9} + 7$) тоонд хуваагаад үлдэгдлийг хэвлэх ёстой.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n, m$ $(2 ≤ n ≤ 10^{5}; 1 ≤ m ≤ 10^{5})$ байх ба харгалзан граф дахь оройнууд болон ирмэгүүдийн тоо юм. Дараагийн $m$ мөрөнд ирмэгүүдийн тайлбар байх ба $i$-р мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $a_{i}, b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ n)$ байх буюу $i$-р ирмэгээр холбогдсон оройнуудын дугаар юм.

Дараагийн мөрөнд бүхэл тоо $k$ $(1 ≤ k ≤ 10^{5})$ байх ба сонирхож буй хос оройнуудын тоо юм. Дараагийн $k$ мөрөнд сонирхож буй хос оройнуудын жагсаалт байна: $i$-р мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $x_{i}$, $y_{i}$ $(1 ≤ x_{i}, y_{i} ≤ n; x_{i} ≠ y_{i})$ байх ба $i$-р хос оройн дугаарууд юм.

Өгөгдсөн граф нь оройн кактус байна. Граф нь давталт болон давхар ирмэг агуулахгүй. Графын оройнуудыг $1$-c $n$ хүртэл дугаарлагдсан гэж үз.

Гаралт

$k$ мөр хэвлэнэ: $i$-р мөрөнд $x_{i}$ оройгоос эхлээд $y_{i}$ оройд дуусах ялгаатай энгийн замуудын тоог $1000000007$ ($10^{9} + 7$) тоонд хуваагаад гарсан үлдэгдлийг илэрхийлэх нэг бүхэл тоог хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
10 11
1 2
2 3
3 4
1 4
3 5
5 6
8 6
8 7
7 6
7 9
9 10
6
1 2
3 5
6 9
9 2
9 3
9 10
Гаралт
2
2
2
4
4
1
Сэтгэгдлүүдийг ачааллаж байна...