D. Дима ба бактер

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

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

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

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

Дима бактерийн биологийг судлаж эхэлсэн ба судалгааны үр дүнд бактерийн $k$ төрлийг олж нээсэн. Одоо түүний лабораторид нийтдээ $n$ бактер байгаа ба $i$-р бактерийн төрөл нь $c_{i}$ байна. Эвтэйхэн байх үүднээс бид бүх бактериудыг $1$-c $n$ хүртэл дугаарлагдсан гэж үзнэ. $c_{i}$ төрлийн бактериудыг хүртэл дугаарлана.

Тусгай багажны тусламжтайгаар Дима нэг бактериас өөр бактерруу энерги шилжүүлж чадна. Мэдээж уг багажын хэрэглээ нь үнэгүй биш. Дима нэг бактериас нөгөөд энерги шилжүүлэх $m$ арга мэднэ. $i$ дугаартай арга нь $u_{i}$, $v_{i}$ ба $x_{i}$ бүхэл тоонуудаар тодорхойлогдох ба энэ арга нь $u_{i}$ дугаартай бактериас $v_{i}$ дугаартай бактерруу эсвэл эсрэг чиглэлд $x_{i}$ доллараар энерги дамжуулж болохыг илэрхийлнэ.

Димагийн ахлах (Инна) хэрвээ тухайн төрлийн дурын бактериас ижил төрлийн өөр дурын бактерруу (ижил төрлийн дурын хоёр бактерийн хооронд) энергийг тэг өртөгтэйгээр дамжуулах зам (чиглэлгүй байж болно) байвал төрлийн тархалт зөв гэж хэлнэ.

Зөв төрлийн тархалтийн хувьд энерги шилжүүлэх өртөг нь зөвхөн бактерийн төрлөөс хамаарах бол Иннад төрлийн тархалт зөв эсэхийг тодорхойлоход туслана уу. Хэрвээ зөв бол $k × k$ хэмжээтэй $d$ матриц хэвлэ. Энэ матрицийн $d[i][j]$ нүд нь $i$ төрлийн бактериас $j$ төрлийн бактерруу энерги дамжуулах боломжит хамгийн бага өртөгтэй тэнцүү байх ёстой.

Оролт

Эхний мөрөнд гурван бүхэл тоо $n, m, k$ $(1 ≤ n ≤ 10^{5}; 0 ≤ m ≤ 10^{5}; 1 ≤ k ≤ 500)$ байна. Дараагийн мөрөнд $k$ бүхэл тоо $c_{1}, c_{2}, ..., c_{k}$ $(1 ≤ c_{i} ≤ n)$ байна. Дараагийн $m$ мөр бүрт гурван бүхэл тоо $u_{i}, v_{i}, x_{i}$ $(1 ≤ u_{i}, v_{i} ≤ 10^{5}; 0 ≤ x_{i} ≤ 10^{4})$ байна. байх нь тодорхой.

Гаралт

Хэрвээ Димагийн төрлийн тархалт нь зөв байвал «$Yes$» тэмдэгт мөрийг хэвлээд $k$ мөр хэвлэнэ: $i$-р мөрөнд $d[i][1], d[i][2], ..., d[i][k]$ $(d[i][i] = 0)$ бүхэл тоонуудыг хэвлэ. Хэрвээ $i$ бактериас $j$ бактерруу энерги дамжуулах арга байхгүй бол $d[i][j]$-н утга -1 байна. Хэрвээ төрлийн тархалт зөв биш байвал «$No$» гэж хэвлэ.

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

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

Оролт
4 4 2
1 3
2 3 0
3 4 0
2 4 1
2 1 2
Гаралт
Yes
0 2
2 0
Оролт
3 1 2
2 1
1 2 0
Гаралт
Yes
0 -1
-1 0
Оролт
3 2 2
2 1
1 2 0
2 3 1
Гаралт
Yes
0 1
1 0
Оролт
3 0 2
1 2
Гаралт
No
Сэтгэгдлүүдийг ачааллаж байна...