Description

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

Format

Input

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

Output

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

Samples

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

-1
1
1

Limitation

30%的数据，N<=1000,M<=1000 100%的数据，1<=N<=200000,1<=m<=400000.