Polish version    English version  
  History of OI -> X OI 2002/2003 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Rules
For contestants
Helpful resources
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
X Olympiad in Informatics 2002/2003

Problem: Monkeys
Author: Andrzej Gasienica-Samek

There are n monkeys on a tree. They are numbered from 1 to n. The monkey number 1 clutches a branch by its tail. Remaining monkeys either are held by other monkeys, hold on to other monkeys or both. Each monkey can use two hands and can hold at most one other monkey in each hand (gripping its tail). Starting from the moment 0, at each second one monkey releases its grip of one hand. This may cause some monkeys fall down onto the ground, where they can continue releasing their grips (the time of falling is negligibly small).

Task

Write a program which:
  • reads from the standard input the description of how the monkeys hold together and in what order they release their grips,
  • for each monkey computes the time it falls down onto the ground,
  • writes the result to the standard output.

Input

The first line of the standard input consists of two positive integers n and m, 1 <= n <= 200000, 1 <= m <= 400000. The number n denotes the number of monkeys, and the number m denotes the time (in seconds) we observe the monkeys. Next n lines contains the description of the initial situation. In the (k + 1)-st line (1 <= k <= n) there are two integers denoting the numbers of monkeys that are hold by the monkey number k. The former is the number of the monkey that is hold by the left hand, and the latter - by the right hand. The number -1 denotes that the monkey's hand is free. The following m lines denote the result of the observation of the monkeys. In the i-th of those lines (1 <= i <= m) there are two integers. The former is the number of the monkey, and the latter is the number of its hand (1 - left, 2 - right) the monkey releases its grip of, in the moment i - 1.

Output

Your program should write to the standard output exactly n integers, one per line. The number of the i-th line should denote the moment the i-th monkey fell down onto the ground, or should be equal -1 if the monkey has not fallen down onto the ground during the observation.

Example

For the following input data:
3 2
-1 3
3 -1
1 2
1 2
3 1
the correct answer is in the following output:
-1
1
1



Print friendly version