C. Цанын бааз

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

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

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

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

Нэгэн цанын бааз Валрусланд-д баригдахаар төлөвлөгджээ. Тэгсэн хэдий ч уг төсөл нь одоо хэр нь барилгын шатандаа явагдаж байгаа юм. Ихээхэн том хэмжээний газарт барилгын ажил явагдахаар болсон байв. Уг газар нь $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг цанын уулзвар агуулах бөгөөд анхандаа цанын уулзварууд нь ямар нэгэн замаар холбогдоогүй байв.

Барилгын ажлын явцад $m$ ширхэг 2 чиглэлтэй цанын зам баригдах ёстой байв. Түүнчлэн замууд нь нэг нэгнийхээ араас баригдах юм: эхлээд $1$ дугаартай зам баригдах ба дараа нь $2$ дугаартай гэх мэтчилэн баригдах юм. $i$-дахь зам нь $a_{i}$ болон $b_{i}$ гэсэн дугаартай уулзваруудыг холбох ажээ.

Трак гэдэг нь дараах шинж чанартай замын маршрутыг хэлнэ:

  • Уг замын маршрут нь битүү байх юм. Өөрөөр хэлбэл энэ нь нэг ижил уулзвараас эхлэх ба төгссөн байна.
  • Уг замын маршрут нь дор хаяж нэг ширхэг зам агуулсан байна.
  • Уг замын маршрут нь нэг замаар нэгээс олон удаа явахгүй боловч ямар ч уулзвараар хэдэн ч удаа зорчин өнгөрсөн байж болно.

Цанын баазыг хоосон биш замын олонлог гэж үзэх бөгөөд уг олонлог нь яг нэг трак нь сонгогдсон олонлогийн зам болгоны дагуу явж өнгөрсөн байхаар нэг болон хэд хэдэн трак-уудад хуваагдаж болдог байх юм. Түүнчлэн трак болгон нь зөвхөн сонгогдсон олонлогийн замуудаас тогтох бөгөөд цанын бааз нь холбоост байх албагүй.

2 цанын баазын хувьд хэрэв тэдгээр нь ялгаатай замуудын олонлогоос тогтож байвал эдгээр 2 баазыг ялгаатай гэж үзнэ.

Шинэ зам бүрийг барьж дууссаны дараагаар Валрусландын засгийн газар аль хэдийн баригдсан замуудын дэд олонлог дээр суурилсан цанын баазыг сонгох хэчнээн янзын боломжит арга байгааг олж мэдэхийг хүсжээ. Тиймээс засгийн газар танаас уг бодлогыг шийдэж өгөхийг хүсжээ.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($2 ≤ n ≤ 10^{5}, 1 ≤ m ≤ 10^{5}$) өгөгдөнө. Эдгээр нь харгалзан цанын уулзварын тоо болон замын тоог илэрхийлнэ. Дараагийн $m$ ширхэг мөрөнд замуудын тайлбар нь баригдсан дарааллаараа өгөгдөнө. Зам болгон нь хос бүхэл тоо $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}$)-аар өгөгдөх ба эдгээр нь уг замаар холбогдож буй уулзваруудын дугааруудыг илэрхийлнэ. Түүнчлэн хос уулзварын хооронд нэгээс олон зам байж болохыг анхаарна уу.

Гаралт

$m$ ширхэг мөр хэвлэнэ: $i$-дахь мөрөнд $i$ дугаартай замыг барьж дууссаны дараа цанын баазыг сонгох боломжийн тоог хэвлэх юм. Уг тоонуудыг $1000000009$ ($10^{9} + 9$) модулаар бодон хэвлэх ёстойг анхаарна уу.

Орчуулсан: Баатархүү

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

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

Тэмдэглэл

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

Барилгын ажил явагдаж буй газар нь дараах байдалтай харагдана:

Бид замуудын дэд олонлогийг 3 янзаар сонгож болно:

Эхний болон 2-дахь аргууд дээр та нэг зам сонгож болох юм. Жишээлбэл, 1 - 2 - 3 - 1. Эхний тохиолдол дээр та 1 - 2 - 1 гэсэн замыг сонгож болно.

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