Road Grass Updates and Queries

Farmer John has N pastures (2 ≤ N ≤ 100,000) connected by N-1 bidirectional roads forming a tree (i.e. there is exactly one path between any two pastures). Bessie complains that the roads have no grass. So, Farmer John will perform M operations (1 ≤ M ≤ 100,000) of two types:

• Update: Given two pastures u and v, plant one patch of grass on each road along the unique simple path from u to v.
• Query: Given a road index, output the total number of grass patches planted on that road so far.

Initially each road has 0 patches of grass. The roads are numbered from 1 to N-1 in the order in which they are given in the input. Help Farmer John answer Bessie's questions!

Note that any formula must be expressed in \(\LaTeX\) format. For example, use \(N\) to denote the number of pastures and \(M\) the number of operations.

inputFormat

The first line contains two integers \(N\) and \(M\): the number of pastures and the number of operations.

The next \(N-1\) lines each contain two integers \(u\) and \(v\), indicating a bidirectional road connecting pastures \(u\) and \(v\).

The following \(M\) lines describe the operations. Each operation is in one of the following formats:

• 1 u v: Update operation. Plant one patch of grass on every road on the unique path from pasture \(u\) to pasture \(v\).
• 2 k: Query operation. Output the number of patches on the road with index \(k\) (roads are indexed from 1 to \(N-1\) in the order given in the input).

outputFormat

For each query operation (lines beginning with 2), output one line containing the number of patches planted on the specified road.

sample

4 6
1 2
2 3
2 4
1 1 3
2 2
1 4 3
2 3
2 2
2 1

1
1
2
1