20135번 - 연세 마스크 공장 스페셜 저지

연세대는 코로나 19를 대비하기 위해서 마스크 공장을 만들었다.

마스크를 생산하는 N개의 공간이 있고 각 공간들을 M개의 단방향 통로, 그리고 마스크를 각 공간별로 보내거나 받는 지하 공간이 있다. 임의의 서로 다른 두 공간 사이에 두 개 이상의 통로가 있는 경우와 같은 공간을 잇는 통로가 있는 경우는 없다.

각 공간별로 정수 p_i가 할당되어 있는데, p_i가 양수면 만큼 지하 공간으로부터 마스크를 매 초마다 p_i 개를 받고, 음수면 매 초마다 -p_i개 만큼 지하 공간으로 보내야 한다. 또한, 각 통로별로 매 초마다 최소 보내야 하는 마스크의 개수 s_i, 보낼 수 있는 마스크의 최대 개수 e_i가 주어진다.

마스크를 생산하는 공간과 지하 공간은 매 초마다 마스크를 보낼 때 해당 공간의 마스크의 개수에 변동 사항이 없어야 한다.

이렇게 했을 때, 각각의 통로별로 몇 개의 마스크를 보내야 하는지 구하여라.

다음과 같이 입력이 주어진다.

첫 번째 줄에 답이 있는 경우에는 1, 답이 없는 경우에는 -1을 출력한다.

답이 있는 경우, M개의 줄에 걸쳐 통로별로 매 초마다 보내야 하는 마스크의 개수를 번호 순서대로 출력하시오. 만약에 답이 여러 개인 경우 가능한 아무 경우나 출력하면 된다.

• 1 ≤ N ≤ 200.
• 0 ≤ M ≤ $\min(\frac{N(N-1)}{2},1000)$
• -10,000,000 × max(min(N-1, M), 1) ≤ p_i ≤ 10,000,000 × max(min(N-1, M), 1)
• 1 ≤ u_i, v_i ≤ N, u_i ≠ v_i. (1 ≤ i ≤ M)
• 0 ≤ s_i ≤ e_i ≤ 10,000,000. (1 ≤ i ≤ M)