Yet Another Hamiltonian Path Problem

頂点が $N$ 個ある有向グラフがある。頂点には $1,2,\cdots,N$ の番号が付けられている。

各頂点 $i$ には値 $A_i$ が与えられる。有向辺は次の規則に従って存在する。

• $A_i=0$ のとき、すべての $j<i$ に対して、頂点 $i$ から頂点 $j$ への有向辺が存在する。

このグラフにおいて、すべての頂点をちょうど一度ずつ訪れる経路である ハミルトン路を一つ求めよ。

経路で続けて訪れる二つの頂点の間には、移動する方向の有向辺が存在しなければならない。始点に戻る必要はない。

例えば、$N=4$、$(A_1,A_2,A_3,A_4)=(1,0,1,0)$ のとき、 はハミルトン路である。各頂点をちょうど一度ずつ訪れ、有向辺 、、 がすべて存在するからである。

入力は次の形式で標準入力から与えられる。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

各テストケースについて、ハミルトン路が存在しない場合は一行に -1 を出力する。

ハミルトン路が存在する場合、その経路が訪れる頂点を始点から終点の順に $p_1,p_2,\cdots,p_N$ とする。一行に を空白区切りで出力する。 は の順列でなければならず、すべての に対して、頂点 から頂点 への有向辺が存在しなければならない。

• $1\le T\le 250\,000$.
• $2\le N\le 500\,000$.
• $A_i\in$ ().