题目描述

有N只猴子，第一只尾巴挂在树上，剩下的N-1只，要么被其他的猴子抓住，要么抓住了其他的猴子，要么两者均有。当然一只猴子最多抓两只另外的猴子。现在给出这N只猴子抓与被抓的信息，并且在某个时刻可能某只猴子会放掉它其中一只手的猴子，导致某些猴子落地。求每只猴子落地的时间。

输入格式：

第一行两个数N、M，表示有N只猴子，并且总时间为M-1。接下来N行，描述了每只猴子的信息，每行两个数，分别表示这只猴子左手和右手抓的猴子的编号，如果是-1，表示该猴子那只手没抓其他猴子。再接下来M行，按时间顺序给出了一些猴子放手的信息，第1+N+i行表示第i-1时刻某只猴子的放手信息，信息以两个数给出，前者表示放手的猴子编号，后者表示其放的是哪只手，1左2右。
【数据规模】
30%的数据，N≤1000，M≤1000;
100%的数据，1≤N≤200000，1≤M≤400000。

输出格式：

共输出N行，第i行表示第i只猴子掉落的时刻，若第i只猴子岛M-1时刻以后还没掉落，就输出-1。

输入样例#1：

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

输出样例#1：

-1
1
1