P11352 [NOISG 2024 Finals] Coin

Benson 有 $n$ 枚不同重量的硬币和一个天平。每次将硬币 $x$ 和 $y$ 放在天平上，可以知道它们的相对重量，即 $x$ 是否比 $y$ 更重。 硬币 $x$ 的排名（rank）定义为不比它更重的硬币数量（包括自身）。例如，最轻的硬币的排名是 $1$，次轻的是 $2$，最重的是 $n$。 对于每个硬币，当且仅当基于已有的称量结果可以唯一确定其排名时，称其排名被“确定”（determined）。 你的任务是帮助 Benson 找出每个硬币首次确定排名的称量序号，或者判断它的排名永远无法确定。

- 第一行包含两个用空格分隔的整数 $n$ 和 $m$，表示硬币的数量和称量的次数。 - 接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示硬币 $x$ 比硬币 $y$ 轻。

输出 $n$ 个整数。如果硬币 $i$ 的排名在所有 $m$ 次称量后仍未确定，输出 $-1$。否则，输出首次确定排名的称量序号 $k$（$1 \leq k \leq m$）。

【样例解释】 对于样例 #1： - 硬币 $1$ 的排名在第 $3$ 次称量后确定，输出 $3$。 - 硬币 $2$ 的排名在第 $4$ 次称量后确定，输出 $4$。 - 硬币 $3$ 和 $4$ 的排名无法确定，输出 $-1$。 对于样例 #2： - 每个硬币的排名确定的时间点分别是 $8$，$8$，$5$，$5$，$5$ 和 $6$。 【数据范围】 - $2 \leq n \leq 200,000$ - $1 \leq m \leq 800,000$ - $1 \leq x, y \leq n$ - 硬币之间的所有称量关系形成一个有效的偏序。 | 子任务编号 | 分值 | 限制条件 | |:---:|:---:|:---:| | $0$ | $0$ | 样例测试用例 | | $1$ | $6$ | $1 \leq n \leq 7, 1 \leq m \leq 20$ | | $2$ | $16$ | $1 \leq n \leq 100, 1 \leq m \leq 400$ | | $3$ | $10$ | $1 \leq n \leq 1000, 1 \leq m \leq 4000$ | | $4$ | $68$ | 无额外限制 |