E. Сэнди ба Самар

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

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

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

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

Үндэстэй мод бол үндэс оройгоор сонгогдсон нэг оройтой ямар нэгэн энгийн циклгүй холбогдсон граф юм. Энэ бодлогонд $1$ дугаартай орой үргэлж үндэс байна.

$u$ болон $v$ оройнуудын хамгийн нам ерөнхий орой нь $u$ оройгоос үндэс хүртэлх зам болон $v$ оройгоос үндэс хүртэлх зам хоёрын огтлолцол дээр орших үндсээс хамгийн хол байх оройг хэлнэ. Бид үүнийг $LCA(u, v)$ гэж тэмдэглэх болно.

Сэндид түүний самруудаа хадгалдаг байсан $n$ оройтой үндэстэй мод байсан. Харамсалтай нь усан доорх шуурга түүний модыг салгасан ба тэр бүх ирмэгийг нь санахгүй байгаа. Тэр анхны модны $m$ ирмэгийг сэргээсэн ба $LCA(a_{i}, b_{i}) = c_{i}$ гэж бодож байгаа $q$ ширхэг $a_{i}$, $b_{i}$ ба $c_{i}$ гурвалыг санаж байгаа.

Сэндид түүний санаж байгаа бүх мэдээлэлтэй таарах $1$ орой нь үндэс байх $n$ хэмжээтэй моднуудын тоог тоолоход туслана уу. Хэрвээ тэр алдаа гаргасан ба тийм мод байхгүй бол $0$-г хэвлэ. Хэрвээ нэгэнд нь байгаа ирмэг нөгөө нэгд нь байхгүй хоёр үндэстэй мод нь ялгаатай гэж тооцогдоно.

Оролт

Оролтын эхний мөрөнд гурван бүхэл тоон утга $n$, $m$ ба $q$ ($1 ≤ n ≤ 13, 0 ≤ m < n, 0 ≤ q ≤ 100$) байх ба харгалзан оройн тоо, ирмэгүүдийн тоо ба Сэндигийн санаж буй $LCA$ гурвалуудын тоо.

Дараагийн $m$ мөр бүрт хоёр бүхэл тоон утга $u_{i}$ ба $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}$) байх ба $i$-р ирмэгээр холбогдсон оройнуудын дугаар. Энэ ирмэгүүдийн бүрдэл нь нэг модны ирмэгүүдийн дэд бүрдэл байх нь тодорхой.

Сүүлийн $q$ мөрөнд $a_{i}$, $b_{i}$, $c_{i}$ ($1 ≤ a_{i}, b_{i}, c_{i} ≤ n)$ тоонуудын гурвалуудыг агуулна. Эдгээр гурвалуудын нэг бүр нь $LCA(a_{i}, b_{i}) = c_{i}$-г тодорхойлно. Бүх өгөгдсөн $LCA$ нөхцөлүүдтэй таарах мод оршин байх албагүй.

Гаралт

Бүх нөхцөлүүдтэй таарах $n$ хэмжээтэй моднуудын тоог илэрхийлэх нэг ширхэг бүхэл тоон утгыг хэвлэ.

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

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

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

Тэмдэглэл

Хоёр дахь жишээн дээр зөв хариулт дараах байдлаар харагдана:

Гурав дахь жишээн дээр зөв хариулт дараах байдлаар харагдана:

Дөрөв дахь жишээн дээр хариулт $0$ байна учир нь $LCA$-н мэдээлэл зөрчилдсөн байна.

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