B. Цанын бааз

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

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

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

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

Валера амралтаараа өөрийн юмнуудаа бэлтгээд цанын бааз руу явахаар болжээ..

Тэр цанын аялалд дуртай ч төөрчхөж магадгүйгээ ойлгожээ. Хэн нэгэн түүнд дараах зөвлөгөөгө өгчээ: Бааз нь $n$ ширхэг объекттэй (объектүүд $1$-с $n$ хүртэлх бүхэл тоонуудаар дугаарлагдсан.Объект бүр нь буудал эсвэл уул.

Мөн тэрээр цанын бааз нь олон цанын замтайг мэджээ. $v$ объект бүрийн хувьд $u$-с $v $ -рүү хүрэх зам олддог байх $u$ объект нэг ихдээ нэг л байна. Мөн ямар ч буудлаас өөр нэг объект рүү хүрэх зам олддоггүй нь мэдэгдэж буй.

Валера төөрчих вий гэж айсандаа таниас зам асууж байна. Зам нь $v_1,v_2,...,v_k (k\ge 1)$ объектүүдээс тогтох ба доорх нөхцөлүүдийг хангах ёстой:

  1. $v_1, v_2,...,v_{k-1}$ дугаартай объектүүд уул ба, $v_k$ дугаартай объект буудал байна.
  2. Дурын $i (1\le i \le k) $ бүхэл тоону хувьд $v_i$ объектоос гарсан яг нэг зам олдох ба энэ нь $v_{i+1}$ объект рүү чиглэж байх учиртай.
  3. Зам нь аль болох олон объектоор дамжиж байх ёстой. (ө.х $k$-н хамгийн их утгандаа хүрэх хэрэгтэй)

Валерад тусалж дээрх шинжүүдийг агуулсан зам олно уу!

Оролт

Эхний мөрөнд объектүүдийн тоо $n (1\le n\le 10^5)$ өгөгдөнө.

Дараагийн мөрөнд $n$ ширхэг объектүүдийг тодорхойлох $n$ ширхэг бүхэл тоо зайгаар тусгаарлагдан өгөгдөнө: $type_i$ тэгтэй тэнцэж байвал $i$дэх объект нь уул ба $type_i$ нэгтэй тэнцэж байвал $i$ дэх объект нь буудал байна. Ядаж нэг буудал заавал байна.

Гурав дахь мөрөнд цанын замуудыг тодорхойлсон $a_1,a_2,...,a_n (0\le a_i\le n)$тоонууд зайгаар тусгаарлагдан өгөгднө. Хэрэв $a_i=0$ бол $v$-с рүү $i$ хүрэх зам олддог $v $ объект олдохгүй. Хэрэв $a_i=0$ бол $v$-с рүү $i$ хүрэх зам олддог $v $ объект олдохгүй. Харин $a_i=1 $ байвал $v$-с рүү $i$ хүрэх зам олддог $v $ объект олдоно.

Гаралт

Эхний мөрөнд Валерагийн явж болох замын урт хамгийн ихдээ хэд байхыг илтгэх $k$ тоог хэвлэнэ үү. Хоёр дахь мөрөнд замыг тодорхойлох $v_1,v_2,...,v_k$ $k$ ширхэг бүхэл тоонуудыг хэвлэнэ үү. Олон шийд байвал аль нэгийг нь дураар сонгон хэвлэхэд хангалттай.

Орчуулсан: Төрбат

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

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