B. Баавгай ба мартагдсан мод 3

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

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

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

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

Мод гэдэг нь $n$ орой болон $n-1$ ирмэгээс тогтох холбоост чиглэлгүй граф юм. Оройнууд нь $1$-ээс $n$ хүртэл дугаарлагдсан байна.

Лимак бол жижиг туйлын баавгай ба Рэйдвүүш бол түүний заналт дайсан. Лимак модтой байсан ба Рэйдвүүш үүнийг нь хулгайлжээ. Баавгай одоо маш их гунигтай байгаа ба учир нь тэрээр модныхоо талаар их зүйл санахгүй байгаа -- тэрээр танд зөвхөн 3-н утга $n$, $d$ болон $h$-г хэлж чадна:

  • Мод нь яг $n$ оройтой.
  • Мод нь $d$ диаметртэй байсан. Өөрөөр хэлбэл, $d$ нь 2 оройны хоорондох хамгийн хол зай байсан.
  • Лимак мөн тэрээр модоо $1$-дэх орой дээр үндэслүүлснээ санаж байгаа ба үүний дараа модны өндөр нь $h$ байсан. Өөрөөр хэлбэл, $h$ нь $1$-дэх орой болон бусад оройн хоорондох хамгийн хол зай байсан.

Модны 2 оройн хоорондох зай гэдэг нь эдгээрийн хооронд байх энгийн зам дээрх ирмэгийн тоог хэлнэ.

Лимак-д түүний модыг сэргээхэд тусална уу. Өгөгдсөн нөхцөлийг хангах мод оршин байх эсэхийг шалгана уу. Ийм байх ямар нэгэн мод олоод эдгээрийн ирмэгийг дурын дарааллаар хэвлэнэ үү. Мөн Лимак нь алдаа гаргасан байх боломжтой ба тохиромжтой мод байхгүй байж болно -- ийм үед "-1" гэж хэвлэнэ үү.

Оролт

Эхний мөрөнд 3 бүхэл тоо $n$, $d$ болон $h$ ($2 ≤ n ≤ 100 000, 1 ≤ h ≤ d ≤ n - 1$) өгөгдөнө -- эдгээр нь харгалзан оройны тоо, диаметр болон $1$-дэх орой дээр үндэслэсний дараах өндрийг илэрхийлнэ.

Гаралт

Хэрэв Лимак-ын санаж байгаатай тохирох мод байхгүй байвал, ганц мөрөнд "-1" (хашилтгүйгээр) гэж хэвлэнэ үү.

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

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

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

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

Тэмдэглэл

Доор таны харж буй моднууд нь 1 болон 3-дахь жишээний гаралтад хэвлэгдсэн байна.

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