题目描述

译自 NOISG 2024 Final T4. Coins

本森有 $n$ 枚重量不同的硬币和一台称重天平。每次他将两枚硬币 $x$ 和 $y$ 放在天平上，硬币之间的相对重量将被揭示，从而他知道 $x$ 和 $y$ 中哪枚更重。

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

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

对于 $n$ 枚硬币，帮助本森确定每枚硬币的排名在哪次称重后被确定，或判断其排名永远无法被确定。

输入格式

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

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

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

输出格式

程序需向标准输出输出结果。

输出 $n$ 个整数。如果硬币 $i$ 在所有 $m$ 次称重后排名未被确定，第 $i$ 个整数应为 $-1$。否则，存在某个 $k$，使得硬币 $i$ 在 $k$ 次称重后排名被确定，但在 $k-1$ 次称重后排名未被确定。输出此 $k$ 值。

4 4
2 4
3 1
4 1
2 3

3 4 -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\%$ 的分数。

这个样例满足子任务 $1,2,3,4$ 的限制。

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

8 8 5 5 5 6

这个样例满足子任务 $2,3,4$ 的限制。

数据范围与提示

对于所有子任务，保证：

• $2 \leq n \leq 200000$
• $1 \leq m \leq 800000$
• $1 \leq x[i], y[i] \leq n$，对于所有 $1 \leq i \leq m$
• 存在一组重量使得硬币 $x[i]$ 比硬币 $y[i]$ 轻（对于所有 $1 \leq i \leq m$）。

详细子任务附加限制及分值如下表所示：

对于每个子任务，如果你的程序正确判断每枚硬币在所有 $m$ 次称重后是否排名被确定，你将获得 $50\%$ 的分数。

具体来说，如果输出 $n$ 个整数，满足：

• 若第 $i$ 枚硬币在 $m$ 次称重后排名未被确定，第 $i$ 个整数为 $-1$。
• 若第 $i$ 枚硬币在 $m$ 次称重后排名被确定，第 $i$ 个整数为 $1$ 到 $m$ 之间的任意整数，

则你将获得该子任务 $50\%$ 的分数。