D. Жагсаалтын бэлгүүд

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

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

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

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

Саша том бөгөөд аз жаргалтай гэр бүлд амьдардаг. Эрчүүдийн баяраар гэр бүлийн бүх эрчүүд баяраа өөрсдийн уламжлалаар тэмдэглэх болсон. Сашагийн гэр бүлд $n$ эрчүүд байдаг ба тэднийг $1$-c $n$ хүртэл дугаарлая.

Хүн бүр хамгийн ихдээ нэг аавтай боловч дурын тооны хүүхэдтэй байна.

$A$ дугаартай залуу нь хэрвээ дараах нөхцөлүүдийн ядаж нэг нь хангагдаж байвал $B$ дугаартай залуугийн өвөг болно:

  • $A = B$;
  • $A$ дугаартай залуу $B$ дугаартай залуугийн аав;
  • $A$ дугаартай залуу $C$ дугаартай залуугийн өвөг байх мөн $C$ дугаартай залуу $B$ дугаартай залуугийн аав байх $C$ дугаартай залуу оршин байх.

Мэдээж хэрвээ $A$ дугаартай залуу нь $B$ дугаартай залуугийн өвөг мөн $A ≠ B$ байвал $B$ дугаартай залуу $A$ дугаартай залуугийн өвөг биш байна.

Сашагийн гэр бүлийн уламжлал нь эрчүүдийн баяраар бэлэх бэлэглэх юм. Энгийн байдлаар бэлэг бэлэглэх нь уйтгартай учир жил бүр дараах зүйлс болдог.

  1. $n$ эрэгтэйчүүдээс заримыг нь ямар нэг дарааллаар агуулсан нэр дэвшигчдийн жагсаалтыг бэлдэнэ.
  2. $n$ залуу бүр бэлэг өгөхөө шийднэ.
  3. Бэлэг өгөх хүнээ сонгохдоо $A$ дугаартай залуу жагсаалтыг харах ба хамгийн эхний $B$ дугаартай хүнийг сонгож бэлгээ түүнд өгнө. Энд $B$ дугаартай залуу нь $A$ дугаартай залуугийн өвөг байна. Тодорхойлолтын дагуу хүн өөр өөртөө бэлэг өгч болно.
  4. Хэрвээ жагсаалтад түүний ямар ч өвөг байхгүй бол тэр гунигтай болох ба бэлгээ хэнд ч өгөхгүйгээр баярыг орхин явна.

Энэ жил та баярыг зохион байгуулахаар шийдсэн ба $n$ залуу бүрээс бэлэг өгөх хүний (зөвхөн өвгүүдээс сонгоно) нэрийг нь асуусан. Хэрвээ тэд бэлгүүдээ дээр тодорхойлсон үйл явцын дагуу өгөх бол та бүх хүсэл биелэгдэж байхаар нэр дэвшигчдийн жагсаалтыг гаргаж чадах уу?

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($0 ≤ m < n ≤ 100 000$) байх ба харгалзан Сашагийн гэр бүлийн эрчүүдийн тоо болон гэр бүлийн холбоосуудын тоо байна.

Дараагийн $m$ мөрөнд гэр бүлийн холбоосуудыг тодорхойлно: $(i + 1)$-р мөрөнд хос бүхэл тоо $p_{i}$ ба $q_{i}$ ($1 ≤ p_{i}, q_{i} ≤ n$, $p_{i} ≠ q_{i}$) байх ба энэ нь $p_{i}$ дугаартай залуу нь $q_{i}$ дугаартай залуугийн аав гэдгийг илэрхийлнэ. Дурын хос тоо хамгийн ихдээ нэг л байна, ялгаатай хоёр залуугаас бүрдсэн хос бүрийн дундаас хамгийн багадаа нэг нь өөр нэгнийхээ өвөг биш байна, залуу бүр хамгийн ихдээ нэг аавтай байна.

Дараагийн мөрөнд $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ n$) байх ба $i$-р тоо нь $i$ дугаартай залуу $a_{i}$ дугаартай эрэгтэйд бэлэг өгөхийг хүсч байна гэсэн үг. Бүх $1 ≤ i ≤ n$-н хувьд $a_{i}$ дугаартай залуу $i$ дугаартай залуугийн өвөг байна.

Гаралт

Эхний мөрөнд нэр дэвшигчдийн жагсаалтад байгаа залуусын тоог илэрхийлэх $k$ $(1 ≤ k ≤ n)$ бүхэл тоог хэвлэ.

Тэгээд хосоороо ялгаатай $n$-с хэтрэхгүй эерэг $k$ бүхэл тоог хэвлэ. Жагсаалт дахь залуусын дугаар нь залуучуудын хүсэлтэй таарч байхаар дараалалтай нэг мөрөнд нэг тоо хэвлэнэ.

Хэрвээ хэд хэдэн боломжит жагсаалт байвал алийг нь ч хэвлэж болно. Хэрвээ жагсаалт олдохгүй бол $ - 1$-г нэг мөрөнд хэвлэ.

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

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

Оролт
3 2
1 2
2 3
1 2 1
Гаралт
-1
Оролт
4 2
1 2
3 4
1 2 3 3
Гаралт
3
2
1
3

Тэмдэглэл

Эхний жишээний тайлбар:

  • хэрвээ жагсаалтанд $1$ байхгүй бол эхний болон гурав дахь залуугийн хүсэл биелэгдэхгүй $(a_{1} = a_{3} = 1)$;
  • хэрвээ жагсаалтанд $2$ байхгүй бол хоёр дахь залуугийн хүсэл биелэгдэхгүй $(a_{1} = a_{3} = 1)$;
  • хэрвээ хариултад $1$ нь $2$-н өмнө байвал хоёр дахь залуу эхний залууд бэлэг өгөх хэрэгтэй, гэвч тэр бэлгээ өөртөө өгөхийг хүссэн $(a_{2} = 2)$.
  • хэрвээ нөгөө талаас $2$ дугаартай залуу $1$ дугаартай залуугийн урд байвал гурав дахь залуу бэлгээ хоёр дахь залууд өгөх хэрэгтэй, гэвч тэр эхний залууд өгмөөр байгаа $(a_{3} = 1)$.
Сэтгэгдлүүдийг ачааллаж байна...