D. Чөтгөрийн ном

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

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

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

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

Паладин Манао намагтай газраас эртний чөтгөрийн номын мөр олжээ. Уг газар нь 1-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг байгууллагатай. Намаг дундуур явна гэдэг нь үнэхээр хэцүү тул хүмүүс яг $n - 1$ зам хийжээ. Зам бүр нь ямар нэгэн хос байгууллагуудыг холбох ба 2 урсгалтай зам байх юм. Түүнчлэн ямар ч байгууллага уруу ямар ч бусад байгууллагаас нэг эсвэл хэд хэдэн замаар дамжин хүрэх боломжтой.

2 байгууллагын хоорондох зай гэдэг нь та нэг байгууллагаас нөгөө байгууллага хүрэх хүртлээ туулах хамгийн бага замуудын тоог хэлнэ. Манао чөтгөрийн номын аюулын хүрээ нь $d$ болохыг мэдэж байв. Өөрөөр хэлбэл хэрэв чөтгөрийн ном нь ямар нэгэн байгууллага дээр байрласан бол уг ном нь өөрийн байрлаж буй байгууллагаас $d$ эсвэл $d$-ээс бага зайд байрлах бусад байгууллагуудад аюул учруулах юм.

Манао $m$ ширхэг байгууллага чөтгөрийн номын аюулд өртсөн болохыг олж сонсжээ. Тэдгээрийн дугаарууд нь $p_{1}, p_{2}, ..., p_{m}$ байв. Ном нь өөр байгууллагууд уруу халдсан ч байж болох ба энэ нь яг тодорхой биш болохыг анхаарна уу. Манао аль байгууллагад ном агуулагдаж байгааг тодорхойлохыг хүсжээ. Түүнд уг хүнд даалгаварт тусална уу.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 3-н бүхэл тоо $n$, $m$ болон $d$ ($1 ≤ m ≤ n ≤ 100000; 0 ≤ d ≤ n - 1$) өгөгдөнө. 2-дахь мөрөнд зайгаар тусгаарлагдсан $m$ ширхэг ялгаатай бүхэл тоо $p_{1}, p_{2}, ..., p_{m}$ ($1 ≤ p_{i} ≤ n$) өгөгдөнө. Дараа нь $n - 1$ мөрийн мөр болгонд уг газрын замуудыг дүрсэлнэ. Зам болгон нь зайгаар тусгаарлагдсан хос бүхэл тоо $a_{i}$ болон $b_{i}$-аар өгөгдөх ба энэ нь уг замын төгсгөлийн цэгүүдийг илэрхийлнэ.

Гаралт

Чөтгөрийн номыг агуулж байж болох байгууллагуудын тоог хэвлэнэ. Манао зөрчилтэй мэдээлэл хүлээн авсан байж болох ба ингэснээр ямар ч байгууллага ном агуулаагүй байж болох юм. Ийм тохиолдолд 0 гэж хэвлэнэ үү.

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

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

Оролт
6 2 3
1 2
1 5
2 3
3 4
4 5
5 6
Гаралт
3

Тэмдэглэл

Жишээ 1. Чөтгөрийн номын аюулын хүрээ нь 3-тай тэнцүү ба энэ нь 1 болон 2-р байгууллагуудад халдсан байна. Иймд 3, 4 эсвэл 5-р байгууллагууд нь чөтгөрийн номыг агуулж байж болох юм.

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