QTREE3 - Query on a tree again!


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
majju69: 2024-01-22 11:40:03

What does 0 and 41.57 mean in the judge status ?

c2zi6: 2024-01-05 19:52:00

is there a solution without HLD?

tianjizi: 2023-02-04 03:14:44

replying to llite_27
HLD, use sets to keep track of black nodes in heavy paths

hieunekodesu: 2023-01-10 15:32:26

hmmm just ett and lazy segment

llite_27: 2022-08-17 11:51:44

my code using HLD +BIT +Binary Search
<snip>
Please share if you done using any other method thanks in advance...

[Simes]: Read the footer - Don't post source code here, use the forum.

Last edit: 2022-08-17 12:30:35
evang12: 2022-03-29 02:28:35

You don't need HLD. Just binary lifting and Euler tour are sufficient.

Don't use HLD when you don't need to.

rkas: 2022-01-06 17:22:02

Perfect score is 100 btw.

Last edit: 2022-01-06 17:22:38
princemishra: 2021-07-02 15:18:04

use binary search and hld

Last edit: 2021-07-02 15:18:23

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-RHINO NODEJS PERL6 VB.NET
Resource:VNOI Marathon '08 - Round 6/DivA
Problem Setter: Blue Mary