D. Сэжүүр

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

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

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

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

Шерлок Холмес өөр нэгэн хэргийг мөрдөж байхдаа хэсэг тооны сэжүүрүүд олжээ. Түүнчлэн тэрээр эдгээр сэжүүрүүдийн заримынх нь хооронд шууд холбоос олсон байв. Тодруулбал зарим сэжүүрүүд нь хоорондоо холбоотой байх бөгөөд үүнийг бид шууд холбогдож байна гэж нэрлэх юм. Сэжүүрүүдийн хоорондох шууд холбоос нь харилцан 2 талтай байна. Өөрөөр хэлбэл $A$ болон $B$-ын хооронд шууд холбоос байна гэдэг нь $B$ болон $A$-ын хооронд шууд холбоос байгаа гэсэнтэй ижил утгатай юм. Мөн ямар ч 2 сэжүүрүүдийн хооронд нэгээс ихгүй тооны шууд холбоос оршин байна.

Мэдээж хэрэг Шерлок эдгээр сэжүүрүүдийн хоорондох шууд холбоосуудыг олж чадах байв. Гэвч энэ нь маш их цаг авах бөгөөд энэ хооронд гэмт хэрэгтнүүд нь нуугдаж амжих юм. Иймд уг хэргийг шийдэхийн тулд Шерлок-т бүх сэжүүр болгон нь бусад сэжүүрүүдтэй холбогдсон байх хэрэгтэй байв. Ингэхдээ заавал шууд байдлаар холбогдсон байх албагүй бөгөөд бусад сэжүүрүүдээр дамжин холбогдсон байж болно. Хэрэв $B$-тэй холбогдсон байх $C$ сэжүүр болон $A$ сэжүүрүүдийн хооронд шууд холбоос оршин байвал $A$ болон $B$ сэжүүрүүдийг холбогдсон байна гэж үзэх юм.

Шерлок Холмес уг хэргийг шийдэхийн тулд түүнд хэрэгтэй болох нэмэлт шууд холбоосуудын хамгийн бага тоог тоолжээ. Энэ нь $T$-тэй тэнцүү байв.

Тэгвэл та хэргийг шийдэж болдог байхаар эдгээр сэжүүрүүдийг яг $T$ ширхэг шууд холбоосоор холбох ялгаатай аргуудыг тоог олно уу. Хэрэв аливаа 2 аргын хувьд нэгэнд нь агуулагдах хоорондоо шууд холбоосоор холбогдсон 2 сэжүүр нь нөгөө нэг арга дотор агуулагдаагүй байвал (өөрөөр хэлбэл шууд холбоосоор холбогдоогүй байвал) уг 2 аргыг ялгаатай аргууд гэж үзнэ.

Ялгаатай аргын тоо нь маш том тоо байж болох учраас уг тоог $k$ модулаар бодон хэвлэнэ үү.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 3-н бүхэл тоо $n, m, k$ ($1 ≤ n ≤ 10^{5}, 0 ≤ m ≤ 10^{5}$, $1 ≤ k ≤ 10^{9}$) өгөгдөх ба эдгээр нь сэжүүрүүдийн тоо, Холмес-ийн аль хэдийн олсон шууд холбоосны тоо болон модул авах үйлдлийн хуваагч тоог тус тус илэрхийлнэ.

Дараагийн $m$ ширхэг мөрийн мөр болгонд 2 бүхэл тоо $a$ болон $b$ ($1 ≤ a, b ≤ n, a ≠ b$) өгөгдөх ба эдгээр нь сэжүүрүүдийн хоорондох шууд холбоосыг илэрхийлнэ. Түүнчлэн ямар ч 2 сэжүүр нь хоорондоо нэгээс илүүгүй тооны шууд холбоосоор холбогдсон байна. Мөн сэжүүрүүдийн хоорондох шууд холбоосууд нь харилцан 2 талтай болохыг анхаарна уу.

Гаралт

Бодлогын хариуг $k$ модулаар бодсон утга болох ганц тоог хэвлэнэ үү.

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

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

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

Тэмдэглэл

Эхний жишээнд зөвхөн 2 сэжүүр өгөгдөх ба Шерлок эдгээрийн хооронд байх ямар ч шууд холбоос олоогүй байв ($T$ нь 1-тэй тэнцүү болно). Хэргийн шийдэх цорын ганц арга нь эдгээрийг холбох нэгэн холбоос олох юм.

2-дахь жишээнд нийтдээ 3 сэжүүр өгөгдөх ба Шерлок мөн л эдгээрийн хооронд байх ямар ч шууд холбоос олоогүй байна ($T$ нь 2-той тэнцүү болно). Тэрээр хэргийг шийдэхийн тулд сэжүүрүүдийн хоорондох боломжит 3-н шууд холбоосноос 2-ыг нь сонгох хэрэгтэй ба ингэж сонгох нийтдээ $3$ арга оршин байна.

3-дахь жишээнд нийтдээ 4 сэжүүр өгөгдөх ба мөрдөгч аль хэдийн 1-р болон 4-р сэжүүрүүдийг холбох шууд холбоосыг олсон байх юм ($T$ нь 3-тай тэнцүү болно). Хэргийг шийдэхийн тулд үлдсэн 2 сэжүүрүүдийг сонгох хэрэгтэй ба ингэж сонгох нийтдээ $8$ арга оршин байх юм.

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