Description

一棵树上有n 只猴子. 他们从1 到 n编号. 编号为1 的猴子用它的尾巴盘住了一个树枝. 剩下的猴子要么被其他的猴子钩住要么就是自己用手钩住其他的猴子. 每只猴子都可以用两只手去钩其他的猴子,每只手最多只能钩一只. 从0时刻开始, 每一秒都有一只猴子松开它的一只手. 这也许会造成一些猴子掉落到地上, 我们想要知道它们掉落地上的时间(猴子掉落的速度都非常的快,可以忽略掉落的时间).

Format

Input

第一行包含两个整数n和 m , 1 <= n <= 200000, 1 <= m <= 400000. 整数 n 代表猴子总数, 数 m 代表我们观察猴子的总时间. 接下来 n 行描述初始的情形. 第 (k + 1) 行 (1 <= k <= n ) 有两个整数分别代表猴子k的左手和右手分别抓住了哪两只猴子. -1 代表它的那只手是空的. 接下来m行代表我们观察到的猴子的活动. 第i行有两个整数(1 <= i <= m ) 代表在第i – 1时刻放开手的是哪只猴子和它放开的是哪只手(1 – 左, 2 – 右).

Output

输出n个整数每行一个代表每只猴子掉落到地上的时间, 如果没有掉落, 输出-1.

Samples

3 2


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

-1
1
1