猴子

题目描述

有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