[Poi2003]Monkeys

一棵树上有 $n$ 只猴子，编号为 $1$ 到 $n$。编号为 $1$ 的猴子用尾巴缠住了一根树枝，其余猴子通过用手钩住其他猴子或被其他猴子钩住而悬挂在树上。

每只猴子都可以用左右两只手钩住其他猴子，每只手最多钩住一只猴子。从第 $0$ 时刻开始，每一秒都会有一只猴子松开一只手。这可能导致一些猴子失去与编号为 $1$ 的猴子之间的连接，从而掉落到地面。

猴子掉落的速度非常快，因此忽略其下落所需的时间。请确定每只猴子掉落到地面的时刻。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示猴子的数量和观察持续的时间。

接下来 $n$ 行描述初始状态。第 $k+1$ 行包含两个整数，依次表示编号为 $k$ 的猴子用左手和右手钩住的猴子编号。若其中一只手为空，则对应位置为 $-1$。

接下来 $m$ 行描述观察到的动作。第 $i$ 行包含两个整数，表示在第 $i-1$ 时刻松手的猴子编号，以及它松开的是哪只手。其中，$1$ 表示左手，$2$ 表示右手。

输出格式

输出 $n$ 行，每行一个整数。第 $k$ 行表示编号为 $k$ 的猴子掉落到地面的时刻；如果该猴子始终没有掉落，则输出 $-1$。

样例输入

3 2


-1 3
3 -1
1 2
1 2
3 1

样例输出

-1
1
1

数据范围

• $1\le n\le 2\times 10^5$；
• $1\le m\le 4\times 10^5$；
• 对于初始状态中的每只手，其对应值为 $-1$ 或一只猴子的编号；
• 对于每次松手操作，手的编号为 $1$ 或 $2$。

来源与许可

本题为 POI 2003 试题「Monkeys」，题面与测试数据整理自 BZOJ 2610。

样例 1

输入

3 2


-1 3
3 -1
1 2
1 2
3 1

输出

-1
1
1