题目描述

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$）。

4 4
2 4
3 1
4 1
2 3

3 4 -1 -1

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

8 8 5 5 5 6

提示

【样例解释】

对于样例 #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$
• 硬币之间的所有称量关系形成一个有效的偏序。