트리 숨기기

XOR 스캐너는 정수 수열을 검사하는 장치다. 수열에 있는 모든 수의 비트 XOR 값이 $0$일 때에만 수열을 통과시킨다.

정점이 $n$개인 트리가 있고, 각 정점에는 1부터 $n$까지의 정수 번호가 붙어 있다. 이 트리를 다음 표준 형식으로 적어야 한다.

$n$ $u_1$ $v_1$ $\dots$ $u_{n-1}$ $v_{n-1}$

여기서 $n$은 정점의 수이고, $u_i$와 $v_i$는 $i$번째 간선이 잇는 두 정점이다.

XOR 스캐너가 이 출력을 통과시키기를 원한다. 처음에는 통과하지 않을 수 있으므로, 일부 정점의 번호를 바꿀 수 있다. 번호를 바꾼 뒤에는 모든 정점의 번호가 1 이상 $10^9$ 이하의 서로 다른 정수여야 한다.

각 정점마다 번호를 바꿀 수 있는지가 정해져 있다. 번호를 바꿀 수 있는 정점의 번호를 다시 정해서(원래 번호를 그대로 둘 수도 있다) XOR 스캐너가 출력을 통과시키게 하라. 불가능하면 그렇다고 보고하라.

첫 줄에 정점의 수 $n$ ($2 \leq n \leq 100000$)이 주어진다.

다음 줄에는 $n$개의 정수가 주어진다. $i$번째 수가 $0$이면 $i$번 정점의 번호가 고정되어 있고, $1$이면 바꿀 수 있다.

이어지는 $n-1$개의 줄에는 간선의 양 끝점 $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$)가 한 줄에 하나씩 주어진다.

번호를 다시 붙인 트리가 존재하면, 문제의 형식과 같은 형식으로 출력하라. 간선의 순서와 각 간선의 양 끝점 순서는 입력과 같아야 한다. 출력하는 모든 수의 비트 XOR 값은 $0$이어야 한다.

불가능하면 -1 한 개만 출력하라.