Валера өөртөө-гогцоо болон олон тооны ирмэггүй $n$ оройгоос тогтох чиглэлгүй холбоост графтай байжээ. Граф нь маш сонирхолтой шинж тэмдэгтэй: уг графын орой бүртэй хамгийн ихдээ $k$ ирмэг зэргэлдээ байсан. Тухтай байлгах үүднээс, бид графын оройнууд нь 1-ээс $n$ хүртэл бүхэл тоонуудаар индекслэгдсэн гэж үзнэ.

Нэг өдөр Валера графын оройнуудын нэгнээс нь бусад бүх орой хүртэл хамгийн богино зайнуудыг тооцоод тэдгээрийг $d$ цуваанд бичиж үлдээжээ. Түүнчлэн, цувааны $d[i]$ элемент нь Валера-ын сонгосон оройноос $i$ дугаартай орой хүртэлх хамгийн богино зайг илэрхийлнэ.

Тэгтэл ямар нэгэн засаршгүй аймшигтай зүйл болжээ. Валера анхны графаа алджээ. Тэгсэн хэдий ч, түүнд $d$ цуваа байсаар байгаа юм. Түүнд алдсан графыг сэргээхэд тусална уу.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $n$ болон $k$ $(1 ≤ k < n ≤ 10^{5})$ өгөгдөнө. $n$ тоо нь анхны графын оройны тоог илэрхийлнэ. $k$ тоо нь анхны графын орой бүртэй хамгийн ихдээ $k$ ирмэг зэргэлдээ байна гэдгийг илэрхийлнэ.

2-дахь мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд $d[1], d[2], ..., d[n]$ $(0 ≤ d[i] < n)$ өгөгдөнө. $d[i]$ тоо нь Валера-ын сонгосон оройноос $i$ дугаартай орой хүртэлх хамгийн богино зайг илэрхийлнэ.

Гаралт

Хэрэв Валера өөрийн тэмдэглэлдээ алдаа гаргасан ба шаардлагатай граф нь оршин байхгүй байвал эхний мөрөнд -1 гэсэн тоог хэвлэнэ үү. Бусад тохиолдолд, эхний мөрөнд бүхэл тоо $m$ $(0 ≤ m ≤ 10^{6})$-г хэвлэнэ -- энэ нь олдсон графын ирмэгийн тоог илэрхийлнэ.

Дараагийн $m$ мөрийн мөр болгонд зайгаар тусгаарлагдсан 2 бүхэл тоо $a_{i}$ болон $b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i})$-г хэвлэх ба, эдгээр нь $a_{i}$ болон $b_{i}$ дугаартай оройнууд нь ирмэгээр холбогдсон гэдгийг илэрхийлнэ. Граф нь өөртөө-гогцоо болон олон тооны ирмэг агуулахгүй. Хэрэв олон тооны хариулт байвал, алийг нь ч хэвлэсэн болно.