Tailed Sungwon Monkeys

There are N Sungwon monkeys hanging from a tree, and each monkey can use both hands. Monkey 1 is hanging from a branch by its tail. Every other monkey may hold another monkey with its left or right hand, may be held by other monkeys, or both.

Each hand is an independent connection. If two monkeys are connected by more than one hand, releasing one hand removes only that one connection; any remaining hand connection still supports them.

Starting at time 0, exactly one specified monkey releases either its left hand or its right hand every second. Immediately after a hand is released, every monkey that is no longer connected to monkey 1 through hand connections falls to the ground. Determine the first time each monkey falls. Some monkeys may never fall.

The first line contains the number of monkeys N and the number of hand-release events M.

• 1 <= N <= 200,000
• 1 <= M <= 400,000

Each of the next N lines contains two integers for monkey i: the monkey held by its left hand and the monkey held by its right hand, in that order. If that hand holds no monkey, the value is -1.

Each of the next M lines contains a monkey number and a hand number for one release event, in chronological order. Hand number 1 means the left hand, and 2 means the right hand. The first event happens at time 0, the next at time 1, and so on.

For monkeys 1 through N, print the first time that monkey falls, one per line. If a monkey never falls, print -1.

A monkey does not fall as long as it remains connected to monkey 1 through some hand connection. When the last connection from monkey 1 to a component disappears, every monkey in that component falls at that time.