QTREE3 - Query on a tree again!

no tags 

You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N. In the start, the color of any node in the tree is white.

We will ask you to perfrom some instructions of the following form:

  • 0 i : change the color of the i-th node (from white to black, or from black to white);
    or
  • 1 v : ask for the id of the first black node on the path from node 1 to node v. if it doesn't exist, you may return -1 as its result.

Input

In the first line there are two integers N and Q.

In the next N-1 lines describe the edges in the tree: a line with two integers a b denotes an edge between a and b.

The next Q lines contain instructions "0 i" or "1 v" (1 ≤ i, v ≤ N).

Output

For each "1 v" operation, write one integer representing its result.

Example

Input:
9 8
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
1 3
0 8
1 6
1 7
0 2
1 9
0 2
1 9 

Output:
-1
8
-1
2
-1

Constraints & Limits

There are 12 real input files.

For 1/3 of the test cases, N=5000, Q=400000.

For 1/3 of the test cases, N=10000, Q=300000.

For 1/3 of the test cases, N=100000, Q=100000.


hide comments
joney_000: 2016-01-11 11:04:21

how to know how many file gives WA or TLE since score is zero for both case.

hippie: 2015-12-11 11:02:03

easy peasy :P straightforward HLD should pass

wohenshuai: 2015-11-28 01:32:59

what's means "0",My solution "a+b problem" got ac..

Luis Manuel Díaz Barón: 2015-04-23 15:16:29

100 points on the first attempt

Gary Ye: 2014-07-05 13:57:50

Wow, cin + cout with ios::sync_with_stdio(false) can get you TLE. I've debugged a 100pt solution for like > 1 hour just because of this. Guys use printf / scanf.

圣龙族骑士: 2014-06-29 11:19:40

爆栈

nika: 2013-11-27 13:17:06

I'm getting 41.67 points, can anyone halp me? plz

hahaha: 2013-11-24 02:30:45

100 is AC

jiangz: 2012-03-06 08:49:22

why I get zero mark after accepting 11 points?

Stumble Xia: 2011-07-21 02:14:08

the result of judging is 91.67,AC?

Last edit: 2011-07-21 02:15:51

Added by:Fudan University Problem Setters
Date:2008-06-14
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS NODEJS PERL 6 VB.net
Resource:VNOI Marathon '08 - Round 6/DivA
Problem Setter: Blue Mary