25892번 - Zero AAMP Currents 스페셜 저지다국어

문제

Thomas Edison stumbled upon an alien electrical device that appears to break known laws of physics! The device consists of $n$ batteries connected by $m$ unidirectional wires, which we will represent as vertices and edges that form a graph. The $i$-th wire is directed from battery $v_i$ to battery $u_i,ドル $v_i \ne u_i$. Let $(v_i → u_i)$ denote such a wire.

To make this device work, Thomas must assign a current strength to each wire such that this assignment results in a successful configuration. For a configuration to be successful, two conditions must be met:

1. All current strength values are non-zero integers in the range $[-1000, 1000]$ AAMP (Alien Amperes).
2. For every cycle found in this device, the sum of AAMP values from all wires in it must be 0ドル$. A cycle is a sequence of edges (wires) $(a_1 → a_2),ドル $(a_2 → a_3),ドル $\dots,ドル$(a_{k-1} → a_k),ドル $(a_k → a_1)$. If edges $(x → y)$ and $(y → x)$ both exist, they also form a cycle – the wires are unidirectional.

Help him with this task.

입력

The first line contains two integers $n$ and $m$ – the number of batteries and the number of wires in the device, respectively. Next, $m$ lines contain two integers each $v_i$ and $u_i,ドル which mean that the $i$-th wire goes from battery $v_i$ to $u_i$.

출력

Print $m$ lines containing one number each: the $i$-th number should be the current strength of $i$-th wire (in AAMP). Each number should be non-zero and in the range of $[-1000, 1000]$. If multiple answers exist, you may print any one of them.

제한

• 1ドル ≤ n ≤ 10^5$
• 1ドル ≤ m ≤ 2 \cdot 10^5$
• 1ドル ≤ v_i , u_i ≤ n,ドル $v_i \ne u_i$

노트

Note that there can be multiple wires from battery $x$ to $y$. Also note that wire $(x → y)$ with strength 3ドル$ AAMP is not the same as $(y → x)$ with strength $-3$. As mentioned before, wires are unidirectional and can have a negative current strength - that’s one of the mysteries of this device ...