파이프

호섬(Hotham) 시가 또다시 최고의 악당 제스터(the Jester)에게 공격받고 있다. 이번 목표는 호섬의 상수도이다. 호섬의 담수는 $N$개의 저수조에 저장되며, 저수조들은 $M$개의 파이프로 연결되어 있다. 임의의 저수조에서 다른 임의의 저수조로 가는 경로가 (여러 파이프를 거치더라도) 적어도 하나 존재한다. 또한 모든 파이프는 서로 다른 두 저수조를 연결하며, 임의의 두 저수조 사이에는 파이프가 최대 하나만 존재한다.

제스터는 일부 파이프를 뚫어 물을 빼내고 있다. 장난기 넘치는 성격 때문에, 제스터는 어느 파이프에서든 빼내는 물의 양이 항상 짝수 세제곱미터 매초($\text{m}^3/\text{s}$)가 되도록 했다. 저수조 $u$와 $v$를 잇는 파이프에서 $2d\ \text{m}^3/\text{s}$의 물을 빼내면, $u$와 $v$는 각각 $d\ \text{m}^3/\text{s}$씩 물을 잃는다.

더 헷갈리게도, 제스터는 뚫린 일부 파이프에는 물을 빼내는 대신 오히려 물을 주입하기도 한다. 마찬가지로 어느 파이프든 주입하는 물의 양은 짝수 $\text{m}^3/\text{s}$이다. 저수조 $u$와 $v$를 잇는 파이프에 $2p\ \text{m}^3/\text{s}$의 물을 주입하면, $u$와 $v$는 각각 $p\ \text{m}^3/\text{s}$씩 물을 얻는다. 각 저수조의 물 양 순변화량은 그 저수조에 연결된 파이프들로부터 얻고 잃은 값의 총합이다. 형식적으로, 어떤 저수조가 물을 각각 $2d_1, 2d_2, \dots, 2d_a\ \text{m}^3/\text{s}$ 빼내는 파이프들과 물을 각각 $2p_1, 2p_2, \dots, 2p_b\ \text{m}^3/\text{s}$ 주입하는 파이프들에 연결되어 있다면, 이 저수조의 물 양 순변화량은 $p_1 + p_2 + \dots + p_b - d_1 - d_2 - \dots - d_a$이다.

호섬 시장은 저수조에는 센서를 설치했지만 파이프에는 설치하지 않았다. 따라서 각 저수조의 물 순변화량은 관측할 수 있지만, 각 파이프에서 얼마나 물이 빠지거나 주입되는지는 알 수 없다.

당신의 임무는 시장을 돕는 프로그램을 작성하는 것이다. 저수조 연결망 전체와 각 저수조의 순변화량이 주어졌을 때, 이 정보만으로 제스터의 계획을 유일하게 결정할 수 있는지 판단하라. 각 파이프에서 물을 얼마나 빼거나 주입했는지에 대한 가능한 경우가 정확히 하나뿐일 때 계획을 유일하게 결정할 수 있다고 한다. 이 값들이 모든 파이프에서 같을 필요는 없음에 유의하라. 가능한 경우가 정확히 하나라면 그 경우를 출력하라.

첫째 줄에 두 정수 $N$(호섬의 저수조 수)과 $M$(파이프 수)이 주어진다. 다음 $N$개의 줄에는 각각 정수 $c_i$가 하나씩 주어지며, 이는 저수조 $i$($1 \le i \le N$)의 순변화량이다. 이 $N$개 줄 중 $i$번째 줄에 $c_i$가 있다. 그다음 $M$개의 줄에는 각각 두 정수 $u_i$와 $v_i$($1 \le u_i, v_i \le N$)가 주어진다. 각 줄은 저수조 $u_i$와 $v_i$ 사이에 파이프가 있음을 나타낸다. 이 $M$개 줄 중 $i$번째 줄에 $u_i$와 $v_i$가 있다.

입력은 항상 제스터가 실제로 만들어 낼 수 있는 저수조 변화량의 집합을 나타낸다.

제스터의 계획을 유일하게 결정할 수 없다면 $0$ 하나만 담긴 한 줄을 출력한다. 그렇지 않으면 $M$개의 줄을 출력하며, 각 줄에는 정수 $x_i$가 하나씩 들어간다($1 \le i \le M$). $i$번째 줄에는 $x_i$를 출력한다. 제스터가 $u_i$와 $v_i$를 잇는 파이프에서 물을 $d_i\ \text{m}^3/\text{s}$ 빼낸다면 $x_i = -d_i$로 둔다. 제스터가 그 파이프에 물을 $p_i\ \text{m}^3/\text{s}$ 주입한다면 $x_i = p_i$로 둔다. 제스터가 그 파이프에서 물을 넣지도 빼지도 않는다면 $x_i = 0$으로 둔다.

• $1 \le N \le 100000$
• $1 \le M \le 500000$
• $-10^9 \le c_i \le 10^9$
• 제스터의 계획을 유일하게 결정할 수 있다면 $-10^9 \le x_i \le 10^9$이다.