E. Хар ба Улаан мод

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

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

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

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

[Red and Black tree-г ингэж орчуулсан болно. ^_^]

Танд $n$ оройтой жинтэй мод өгөгджээ. Бүх орой нь хараар, эсвэл улаанаар будагдсан. Хэрвээ бид аль ч оройгоос хамгийн ихдээ $x$ зайд хар орой олж чаддаг бол энэ модыг "үзэсгэлэнтэй" мод гэж нэрлэе.

Хоёр оройн зайг тэдгээрийн хоорондох хамгийн богино зай гэж үзнэ.

Танд Хар ба Улаан мод өгөгдсөн бол хамгийн цөөн удаа өнгө солих үйлдэл хэрэглээд уг модыг "үзэсгэлэнтэй" болго. Өнгө солих үйлдэл нь дурын хоёр оройг сонгож аваад, тэдгээрийн өнгийг солих үйлдэл болно. Жишээ нь та улаан орой $p$, хар орой $q$-г сонгоод нэг үйлдлээр $p$-г хар, $q$-г улаан болгож болно.

Хамгийн цөөн шаардлагатай үйлдлийн тоог хэвлэ.

Оролт

Оролтын эхний мөрөнд $n$, $x$ ($2 ≤ n ≤ 500$; $1 ≤ x ≤ 10^9$) тоо байрлана. Дараагийн мөрөнд зөвхөн $0$ эсвэл $1$ байх $n$ тоо өгөгдөнө. Хэрвээ $i$-р тоо $1$ байвал $i$-р орой хар, эсрэг тохиолдол улаан өнгөтэй байна. Дараагийн $n-1$ мөрөнд модны холбоос өгөгдөнө. $j$ мөрөнд $u_j$ ба $v_j$ оройнууд $w_j$ жинтэй ирмэгээр холбогдсон болохыг илэрхийлэх $u_j$, $v_j$, $w_j ($1 ≤ u_j, v_j ≤ n$; $u_j ≠ v_j$; $1 ≤ w_j ≤ 10^9$) тоонууд байна.

Модны оройнууд $1$-с $n$ хүртэл дугаарлагдсан гэж үзээрэй.

Гаралт

Хамгийн цөөн солих үйлдлийн тоо болох ганц тоог хэвлэнэ.

Хэрвээ модыг яагаад ч "үзэсгэлэнтэй" болгож чадахгүй бол "-1"-г хэвлэ.

Орчуулсан: zoloogg

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

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