题目描述

一棵树上有 $n$ 只猴子。他们从 $1 \sim n$ 编号。编号为 $1$ 的猴子用它的尾巴盘住了一个树枝，剩下的猴子要么被其他的猴子钩住要么就是自己用手钩住其他的猴子。每只猴子都可以用两只手去钩其他的猴子，每只手最多只能钩一只。

从 $0$ 时刻开始，每一秒都有一只猴子松开它的一只手。这也许会造成一些猴子掉落到地上，我们想要知道它们掉落地上的时间（猴子掉落的速度都非常的快，可以忽略掉落的时间）。

输入格式

第一行包含两个整数 $n$ 和 $m$，$n$ 代表猴子总数，$m$ 代表我们观察猴子的总时间。

接下来 $n$ 行描述初始的情形。第 $k$ 行有两个整数，分别代表猴子 $k$ 的左手和右手分别抓住了哪两只猴子，$-1$ 代表它的那只手是空的。

接下来 $m$ 行代表我们观察到的猴子的活动。第 $i$ 行有两个整数，代表在第 $i-1$ 时刻放开手的是哪只猴子和它放开的是哪只手（1 – 左，2 – 右）。

输出格式

输出 $n$ 个整数，每行一个整数，代表每只猴子掉落到地上的时间。如果没有掉落，输出 -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$。