31878번 - 트리 스도쿠 스페셜 저지

평범한 방식의 스도쿠에 질린 룰루는 새로운 방식의 스도쿠를 제안했다.

1. $N$개의 정점으로 이루어진 트리와 $N$개의 정수로 이루어진 수열 $A$가 주어진다. 수열 $A$의 $i$번째 원소는 $A_i$이며, 수열 $A$의 원소는 서로 다른 값을 갖는다.
2. 트리의 모든 정점과 수열의 모든 원소를 일대일 대응시킨다. 즉, 트리의 각 정점은 수열의 원소 하나와 대응되며, 대응되는 원소는 서로 다르다.
3. 각 정점은 대응된 원소의 값을 자신의 값으로 정한다. 이때 모든 인접한 두 정점의 값의 합이 서로 달라야 한다. 다시 말해, 트리에서 어떤 인접한 두 정점의 합은 다른 모든 인접한 두 정점의 합과 달라야 한다.

룰루는 이와 같은 스도쿠를 트리 스도쿠라고 부르기로 했다. 위 규칙에 맞추어 트리 스도쿠를 진행해 보자.

첫 번째 줄에 정수 $N$이 주어진다. $(2 \leq N \leq 111\,222)$

두 번째 줄에 수열 $A_1, A_2, \cdots, A_N$이 공백을 사이에 두고 순서대로 주어진다. $(-10^9 \leq A_i \leq 10^9,$ 수열 $A_i$의 원소는 모두 다르며 정수다.$)$

다음 $N-1$개의 줄에 걸쳐 트리의 간선이 a b와 같은 형식으로 주어 진다. 이는 $a$번 정점과 $b$번 정점을 연결하는 간선이 존재하는 것을 의미한다. $(1 \leq a, b \leq N)$

첫 번째 줄에 어느 인접한 두 정점의 값의 합이 다르도록 일대일 대응시키는 방법이 존재한다면 YES, 그렇지 않으면 NO를 출력한다.

방법이 존재할 경우, 다음 줄에 트리의 각 정점과 대응할 수열의 원소 번호를 공백을 사이에 두고 트리의 정점 번호 순서대로 출력한다.

가능한 방법이 여러 가지라면 그중 아무거나 출력한다.