Програмчлалын олимпиадын бодлогын архив

Алгоритмын онолд байдаг гол ойлголтуудын нэг нь рекурс юм. Рекурс гэдэг нь ямар нэг процедур (функц) өөрийгөө шууд эсвэл бусад процедуруудаар дамжуулан дуудахыг хэлнэ. Энэ нь алгоритм зохиох хүчтэй хэрэгсэл боловч болгоомжтой хэрэглэх хэрэгтэй байдаг. Жишээ нь буруу бичсэн рекурсив процедур төгсгөлгүй рекурст орох буюу хэзээ ч биелж дуусахгүй байдалд хүрч болно (яг үнэндээ бол стек санах ой дүүрснээр биелэлт дуусна).
Рекурс нь шууд бус хэлбэрээр (өөр процедуруудаар дамжуулан өөрийгөө дуудах) байж болох тул өгөгдсөн процедур рекурсив мөн эсэхийг тодорхойлоход хэцүү байдаг. Таны даалгавар бол өгөгдсөн процедур тус бүрийг рекурсив байж чадах эсэхийг нь тодорхойлох явдал юм.
P₁, P₂, …, P_n гэсэн n ширхэг процедураас тогтох програмыг авч үзье. Процедур бүрээс ямар өөр процедуруудыг дуудаж болох нь өгөгдсөн байг. Хэрэв дараах нөхцлийг хангасан Q₀, Q₁, …, Q_k процедуруудын дараалал олдож байвал P процедурыг рекурсив байж чадах процедур гэж нэрлэнэ: Q₀ = Q_k = P ба i = 1…k–1 утгуудын хувьд Q_i-1 процедураас Q_i процедурыг дуудаж болдог байна.
Өгөгдсөн процедуруудаас аль нь рекурсив байж чадахыг тодорхойлох програм бич.

Input

Эхний мөрөнд процедуруудын нийт тоо болох n натурал тоо өгөгдөнө (n<1000). Дараагийн n ширхэг мөр тус бүрд нэг процедурыг тодорхойлсон байна. i+1-р мөрийн эхэнд P_i процедураас дуудаж болох бүх процедуруудын нийт тоо байрлах ба түүний араас уг процедуруудын дугаарууд хоосон зайгаар тусгаарлан өгөгдөнө.

Output

Гаралт дээр рекурсив байж чадах процедуруудын дугаарыг өсөх дарааллаар зайгаар тусгаарлан гаргана.

Example

Input:
5
3 2 3 4
1 3 
1 4
1 1
1 4

Output:
1 2 3 4