1170: 黑白学宫

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：1 Solved：1

Description

Alice is given a tree with n nodes indexed from 1 to n. Each edge on the tree can be either black or white, and all edges are initially white.
There are three kinds of operations:
1. Change the color of an edge to black.
2. Change the color of an edge to white.
3. Given a node index, count the sum of the number of black edges on the simple path from all odd-indexed nodes to that node.
Note that a simple path is a path between two nodes that does not visit any node more than once.

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

The first line contains two integers n (1 ≤n≤100,000) and m (1 < m≤100, 000)，separated by a apace.
Here, n represents the number of nodes on the tree, and m represents the total number of operations.

Next, there are n- 1 lines, where the i-th line contains two integers u and v (1 ≤u, v<= n)，representing 
the two nodes connected by the i-th edge on the tree. Following these are m lines, each representing one 
operation. The format of each operation is as follows:

- 1 x: Assign the color black to the edge indexed by x.
- 2 x: Assign the color white to the edge indexed by x.
- 3 x: Count the sum of the number of black edges on the simple path from all odd-indexed nodes to the node
indexed by x.

Output

For each operation 3, output a single integer in a line, indicating the sum of the number of black edges on
the simple path fzom all odd-indexed nodes to the node indexed by x, where x is the parameter of the
operation.

Sample Input Copy 

5 5
1 2
1 3
1 4
1 5
1 1
3 2
3 3
2 1
3 2

Sample Output Copy 

3
0
0

HINT

样例输入2：
11 10
11 2
10 2
1 5
1 4
2 6
4 9
8 5
5 7
2 3
2 1
2 9
2 1
1 1
3 3
1 1
1 8
1 5
2 10
1 8

3 8


样例输出2：
1
2

Source/Category