一棵树上有 $n$ 只猴子，编号为 $1$ 到 $n$。$1$ 号猴子用尾巴抓着一根树枝。其余的猴子要么被其他猴子抓住，要么抓住其他猴子，或者两者兼有。每只猴子可以使用两只手，每只手最多可以抓住另一只猴子（抓着它的尾巴）。从时刻 0 开始，每一秒都有一只猴子松开一只手。这可能会导致一些猴子掉落到地面上，掉落到地面上的猴子可以继续松开它们的手（掉落的时间忽略不计）。

编写一个程序：

• 从标准输入读取猴子之间如何互相抓住以及它们松开手的顺序的描述，
• 计算每只猴子掉落到地面上的时刻，
• 将结果写入标准输出。

输入格式

第一行包含两个正整数 $n$ 和 $m$，$1 \le n \le 200\,000$，$1 \le m \le 400\,000$。其中 $n$ 表示猴子的数量，$m$ 表示我们观察猴子的时间（以秒为单位）。

接下来的 $n$ 行描述了初始状态。在第 $k+1$ 行（$1 \le k \le n$）中，有两个整数，表示被 $k$ 号猴子抓住的猴子的编号。前一个数是被左手抓住的猴子编号，后一个数是被右手抓住的猴子编号。数字 $-1$ 表示该猴子的对应手是空闲的。

接下来的 $m$ 行表示对猴子的观察结果。在这些行中的第 $i$ 行（$1 \le i \le m$）有两个整数。前一个数是猴子的编号，后一个数是它松开的手的编号（1 表示左手，2 表示右手），该动作发生在时刻 $i-1$。

输出格式

输出正好 $n$ 个整数，每行一个。第 $i$ 行的数字表示第 $i$ 只猴子掉落到地面上的时刻；如果该猴子在观察期间没有掉落到地面上，则输出 $-1$。

样例

样例输入 1

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

样例输出 1

-1
1
1