트리에 가중치 부여하기

n개의 정점과 m개의 간선으로 이루어진 연결된 무방향 그래프가 주어진다. 정점에는 1부터 n까지 번호가 매겨져 있다.

n개의 정수 c1, c2, ..., cn이 주어지며, 각각은 - n 이상 n 이하이다. 또한 cv의 홀짝성이 정점 v의 차수의 홀짝성과 같음이 보장된다. 정점의 차수는 그 정점에 연결된 간선의 수이다.

각 정점 v에 대해 그 정점에 연결된 간선들의 가중치 합이 cv가 되도록 각 간선에 - 2·n2 이상 2·n2 이하의 가중치를 적거나, 이것이 불가능하다고 판별해야 한다.

첫째 줄에 정수 n와 m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 105)이 주어진다. 각각 정점의 수와 간선의 수를 나타낸다.

다음 줄에는 n개의 정수 c1, c2, ..., cn ( - n ≤ ci ≤ n)이 주어진다. 여기서 ci는 정점 i에 연결된 간선들의 가중치에 요구되는 합이다. ci의 홀짝성이 정점 i의 차수의 홀짝성과 같음이 보장된다.

다음 m개의 줄에는 그래프의 간선이 설명된다. 이 줄들 중 i-th번째 줄에는 두 정수 ai와 bi (1 ≤ ai, bi ≤ n; ai ≠ bi)이 주어지며, 이는 i-th번째 간선이 정점 ai와 bi를 연결한다는 뜻이다.

주어진 그래프가 연결되어 있으며 루프와 다중 간선을 포함하지 않음이 보장된다.

해가 없다면 "NO"을 출력한다.

그렇지 않다면 "YES"을 출력한 다음 m개의 줄을 출력한다. 그중 i-th번째 줄에는 i-th번째 간선의 가중치 wi ( - 2·n2 ≤ wi ≤ 2·n2)를 출력한다.