C. Шалгах цэгүүд

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

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

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

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

Танай хот $n$ ширхэг уулзвартай. Мөн эдгээр уулзваруудын хооронд $m$ ширхэг нэг чиглэлтэй зам байдаг. Хотын даргын хувьд та эдгээр бүх уулзваруудын аюулгүй байдлыг хангах ёстой юм.

Аюулгүй байдлыг хангахын тулд та хэсэг цагдаагийн шалгах цэгүүд барих хэрэгтэй. Шалгах цэгүүд нь зөвхөн уулзвар дээр баригдаж болно. Хэрэв $i = j$ эсвэл цагдаагийн эргүүлийн машин нь $i$-аас $j$ уруу яваад буцаад $i$-даа эргэн ирж чаддаг бол $i$ уулзвар дээрх шалгах цэг нь $j$ уулзварыг хамгаалж чадах юм.

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

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

Оролт

Эхний мөрөнд танд уулзварын тоо болох бүхэл тоо $n$ өгөгдөнө $(1 ≤ n ≤ 10^{5})$. Дараагийн мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоо өгөгдөнө. $i$-дахь бүхэл тоо нь $i$-дахь уулзвар дээр шалгах цэг барих зардлыг илэрхийлнэ (зардал нь сөрөг биш бүхэл тоо байх ба $10^{9}$-аас хэтрэхгүй байна).

Дараагийн мөрөнд бүхэл тоо $m (0 ≤ m ≤ 3*10^{5})$ өгөгдөнө. Мөн дараагийн $m$ мөрийн мөр болгонд 2 бүхэл тоо $u_{i}$ болон $v_{i} (1 ≤ u_{i}, v_{i} ≤ n; u ≠ v)$ өгөгдөнө. $u_{i}, v_{i}$ хос нь $u_{i}$-аас $v_{i}$ хүртэл явах нэг урсгалтай зам байгааг илэрхийлэх юм. 2 уулзварын хооронд ижил чиглэлтэй нэгээс илүү зам байхгүй байна.

Гаралт

Зайгаар тусгаарлагдсан 2 бүхэл тоо хэвлэнэ. Эхний тоо нь бүх уулзварын аюулгүй байдлыг хангахын тулд шаардагдах боломжит хамгийн бага мөнгөн дүнг илэрхийлнэ. 2-дахь тоо нь хамгийн бага зардлаар аюулгүй байдлыг хангах нийт аргын тоог $1000000007$ $(10^{9} + 7)$ модулаар бодсон утга байна.

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

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

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