2022 Fall Waterloo Local Contest, Problem A

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^\text{th}~ wire is directed from battery ~v_i~ to battery ~u_i~, ~v_i \ne u_i~. Let ~(v_i \to 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 ~[-1\,000, 1\,000]~ 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 \to a_2), (a_2 \to a_3), \dots, (a_{k-1} \to a_k), (a_k \to a_1)~. If edges ~(x \to y)~ and ~(y \to x)~ both exist, they also form a cycle - the wires are unidirectional.

Help him with this task.

Constraints

~1 \le n \le 10^5~

~1 \le m \le 2 \cdot 10^5~

~1 \le v_i, u_i \le n~

~v_i \ne u_i~

Input Specification

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^\text{th}~ wire goes from battery ~v_i~ to ~u_i~.

Output Specification

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

Sample Input

4 7
1 2
2 3
3 1
1 4
2 4
1 4
3 2

Sample Output

-1
-1
2
-2
-1
-2
1

Note

Note that there can be multiple wires from battery ~x~ to ~y~. Also note that wire ~(x \to y)~ with strength ~3~ AAMP is not the same as ~(y \to 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…