Yet Another Hamiltonian Path Problem

如果 $A_1=0$，那么顶点 $1$ 没有任何出边。因此，如果存在哈密顿路径，顶点 $1$ 必须是路径的最后一个顶点。

类似地，如果 $A_N=1$，那么顶点 $N$ 没有任何出边。因此，此时顶点 $N$ 也必须是任意哈密顿路径的最后一个顶点。

所以当 $A_1=0$ 且 $A_N=1$ 时，两个不同的顶点都必须成为路径的最后一个顶点，这是不可能的，因此不存在哈密顿路径。

在其余情况下，我们总能直接构造一条哈密顿路径。

假设 $A_N=0$。先将所有满足 $A_i=1$ 的顶点按编号升序输出，再将所有满足 $A_i=$ 的顶点按编号降序输出。在第一部分中，当前顶点的值为 ，且下一个顶点的编号更大，因此所需的有向边一定存在。在第二部分中，当前顶点的值为 ，且下一个顶点的编号更小，因此所需的有向边也一定存在。如果两部分都非空，那么第一部分最后一个顶点的编号小于 ，而第二部分的第一个顶点就是 ，所以两部分之间也存在所需的有向边。

如果 $A_N=1$，由于当前不是不可能的情况，因此必有 $A_1=1$。此时先将所有满足 $A_i=$ 的顶点按编号降序输出，再将所有满足 的顶点按编号升序输出。每一部分内部的边都由与上面相同的理由保证存在。如果两部分都非空，那么第一部分最后一个顶点的编号大于 ，而第二部分的第一个顶点就是 ，所以两部分之间也存在所需的有向边。

每个顶点只会被处理常数次，因此每个测试用例的时间复杂度为 $O(N)$，总时间复杂度为 $O(\sum N)$。额外空间复杂度为 $O(N)$。

Solution written by GPT5.6