Thomas Edison 偶然发现了一个外星电气设备，它似乎打破了已知的物理定律！ 该设备由 $n$ 个电池和 $m$ 条单向导线组成，我们将它们表示为图中的顶点和边。第 $i$ 条导线从电池 $v_i$ 指向电池 $u_i$，$v_i \neq u_i$。记作 $(v_i \to u_i)$。

为了使该设备正常工作，Thomas 必须为每条导线分配一个电流强度，使得该分配方案成为一个成功的配置。要使配置成功，必须满足以下两个条件： 1) 所有电流强度值均为 $[-1000, 1000]$ 范围内的非零整数（单位为 AAMP，即外星安培）。 2) 对于设备中发现的每一个环，环中所有导线的 AAMP 值之和必须为 $0$。环是一个由边（导线）组成的序列 $(a_1 \to a_2), (a_2 \to a_3), \dots, (a_{k-1} \to a_k), (a_k \to a_1)$。如果边 $(x \to y)$ 和 $(y \to x)$ 同时存在，它们也构成一个环——导线是单向的。

请帮助他完成这项任务。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示电池的数量和导线的数量。接下来 $m$ 行，每行包含两个整数 $v_i$ 和 $u_i$，表示第 $i$ 条导线从电池 $v_i$ 指向 $u_i$。

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le v_i, u_i \le n, v_i \neq u_i$

输出格式

输出 $m$ 行，每行包含一个数字：第 $i$ 个数字应为第 $i$ 条导线的电流强度（单位为 AAMP）。每个数字必须是非零整数，且在 $[-1000, 1000]$ 范围内。如果存在多种答案，你可以输出其中任意一个。

样例

输入格式 1

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

输出格式 1

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

说明

注意，从电池 $x$ 到 $y$ 可能存在多条导线。还要注意，强度为 $3$ AAMP 的导线 $(x \to y)$ 与强度为 $-3$ 的 $(y \to x)$ 并不相同。如前所述，导线是单向的，并且可以具有负的电流强度——这是该设备的奥秘之一……