分数: 400 点
问题陈述
有 N 卡片和 N 成堆的卡片。
卡片和牌堆已编号 1, 2, \ldots, N。最初,堆 i 仅包含卡 i.
对每个执行以下操作 i = 1, 2, \ldots, Q 按顺序:
- 移动卡 C_i 以及堆叠在卡片顶部的所有卡片 C_i,保留其顺序,位于卡片顶部 P_i。保证在执行操作之前,卡 C_i 和 P_i 位于不同的堆中,并且卡片 P_i 在一些堆的顶部。
所有操作完成后求每堆牌的数量。
约束
- 1 \leq N, Q \leq 3 \times 10^5
- 1 \leq C_i, P_i \leq N
- 按顺序执行操作时,在每次操作之前,卡片 C_i 和 P_i 位于不同的堆中。
- 按顺序执行操作时,在每次操作之前,卡 P_i 在一些堆的顶部。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q C_1 P_1 C_2 P_2 \vdots C_Q P_Q
输出
让 A_i 是牌堆中的牌数 i 在最后。输出 A_1, A_2, \ldots, A_N 按此顺序,用空格分隔。
样本输入 1
5 4 1 3 4 5 1 4 4 2
示例输出 1
0 3 1 0 1
操作顺序如下图所示。

示例输入 2
7 8 3 1 5 4 2 5 5 7 2 3 6 2 3 4 5 1
示例输出 2
2 0 0 4 0 0 1