Change Segment Colors

There is a map with n segments. Every segment on the map can either be a red segment or a black segment. There is no closed loop in the map (i.e., no cycles). Initially, all segments on the map are red. You need to perform m operations on the map, and there are two types of operations:

1. Given two stations a and b:
   • For every station x on the path from a to b (including a and b), change all segments connected to x to red.
   • Then convert all the segments on the path from a to b into black.
2. Given two stations a and b:
   • Calculate how many black segments exist on the path from a to b.

Input Format:

The input is an array of strings:

• The first string contains two integers n and m, where n is the number of stations and m is the number of operations.
• The next n - 1 strings, each containing two integers u and v, indicate that there is a segment between station u and station v.
• The next m strings each contain integers opi, ai, and bi:
  • opi represents the operation type:
    • 1 means the first type of operation.
    • 2 means the second type of operation.
  • ai and bi represent the two stations. Note that ai is not equal to bi.

Output Format:

The output is an array of integers. For every second type of operation, output the result as an integer.

Example:

Input:

operations = ["8 5", "1 2", "1 3", "3 4", "4 5", "4 6", "2 8", "2 9", "1 1 6", "1 2 4", "2 1 6", "1 1 5", "2 2 6"]

Output:

[2, 2]

Explanation:

1. For the first operation (1 1 6), the path from station 1 to station 6 is changed to black segments.
2. For the second operation (1 2 4), the path from station 2 to station 4 is changed to black segments.
3. For the third operation (2 1 6), the number of black segments on the path from station 1 to station 6 is 2.
4. For the fourth operation (1 1 5), the path from station 1 to station 5 is changed to black segments.
5. For the fifth operation (2 2 6), the number of black segments on the path from station 2 to station 6 is 2.

This version replaces the LaTeX formatting with simple, structured text to ensure clarity and readability.

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.