Benson 有 $n$ 枚重量各不相同的硬币，以及一个天平。每当他将两枚硬币 $x$ 和 $y$ 放在天平上时，它们之间的相对重量就会显现出来，从而使他知道 $x$ 和 $y$ 哪一枚更重。

硬币 $x$ 的排名等于重量不大于硬币 $x$ 的硬币数量（包括其自身），因此最轻的硬币排名为 1，次轻的硬币排名为 2，以此类推，最重的硬币排名为 $n$。

如果一枚硬币在现有的称重结果下只有唯一可能的排名，则称该硬币的排名是确定的。

对于每一枚硬币，请帮助 Benson 确定使其排名变得确定的第一次称重，或者判定该硬币的排名永远无法确定。

输入格式

程序必须从标准输入读取数据。

第一行包含两个空格分隔的整数 $n$ 和 $m$。

接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示硬币 $x$ 比硬币 $y$ 轻。

输出格式

输出 $n$ 个整数。如果硬币 $i$ 在所有 $m$ 次测量后排名仍不确定，则第 $i$ 个整数应为 $-1$。否则，存在某个 $k$，使得硬币 $i$ 在经过 $k$ 次称重后排名确定，但在经过 $k-1$ 次称重后排名不确定。输出这个 $k$ 的值。

子任务

对于所有子任务，保证：

• $2 \le n \le 200\,000$
• $1 \le m \le 800\,000$
• 对于所有 $1 \le i \le m$，满足 $1 \le x[i], y[i] \le n$
• 存在一组重量分配方案，使得对于所有 $1 \le i \le m$，硬币 $x[i]$ 均比硬币 $y[i]$ 轻。

你的程序将在满足以下限制的输入实例上进行测试：

对于每个子任务，如果你的程序能正确判定每枚硬币在 $m$ 次称重结束时是否确定，你将获得该子任务 50% 的分数。

具体而言，如果你输出 $n$ 个整数，使得：

• 如果第 $i$ 枚硬币的排名在 $m$ 次测量结束时未确定，则第 $i$ 个整数为 $-1$
• 如果第 $i$ 枚硬币的排名在 $m$ 次测量结束时已确定，则第 $i$ 个整数为 $1$ 到 $m$ 之间的任意整数

那么你将获得该子任务 50% 的分数。

样例

样例输入 1

4 4
2 4
3 1
4 1
2 3

样例输出 1

3 4 -1 -1

说明 1

我们在前 3 次测量后可以确定硬币 1 是最重的，但仅看前 2 次测量无法做到这一点。因此，正确输出中的第一个整数是 3。

同样，我们可以在 4 次测量后确定硬币 2 是最轻的，但在 3 次测量后无法确定。因此，正确输出中的第二个整数是 4。

观察到排序 2,4,3,1 和 2,3,4,1 都是硬币重量的有效排序。因此，硬币 3 的排名可能是 2 或 3，两者都与所有称重结果一致，因此硬币 3 的排名永远无法确定。同样，硬币 4 的排名也永远无法确定。

如果你的输出是 1 1 -1 -1，你将获得该子任务 50% 的分数。

样例输入 2

6 8
1 5
5 4
6 2
2 5
4 3
6 1
6 5
2 1

样例输出 2

8 8 5 5 5 6