QTREE3  Query on a tree again!
English  Vietnamese 
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 ith 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 N1 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
Luis Manuel Díaz Barón:
20150423 15:16:29
100 points on the first attempt 

Gary Ye:
20140705 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. 

圣龙族骑士:
20140629 11:19:40
爆栈


nika:
20131127 13:17:06
I'm getting 41.67 points, can anyone halp me? plz 

hahaha:
20131124 02:30:45
100 is AC 

jiangz:
20120306 08:49:22
why I get zero mark after accepting 11 points? 

Stumble Xia:
20110721 02:14:08
the result of judging is 91.67,AC? Last edit: 20110721 02:15:51 
Added by:  Fudan University Problem Setters 
Date:  20080614 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  VNOI Marathon '08  Round 6/DivA Problem Setter: Blue Mary 