Mr. Heart, the ruler of Tree Kingdom, oversees a realm of \(N\) cities connected by \(N-1\) roads, forming a tree. Each road between two cities has a travel cost of 1 unit. Mr. Heart loves to explore his kingdom, and he needs your help to solve some of the challenges he faces on his journey.

You must assist Mr. Heart by answering two types of queries about the travels and paths between different cities:

• \(1 U V \): Calculate the total travel cost between two distinct cities.
• \(2 U V K \): Find the \(k^{th}\) city within path \(U\) to \(V\).  If the \(k^{th}\) city does not exist, print \(-1\).

The first line contains two integers: \(N\) (the number of cities in Tree Kingdom) and \(Q\) (number of queries) (\(1 ≤ N, Q ≤ 10^5\)).
Each of the next \(N-1 \) lines contains two integers \(U, V \; (1 ≤ U, V ≤ N )\).
Each of the next \(Q\) lines describes a query in one of two formats:
\(1 U V\\ 2 U V K \; [U ≠ V] \)
 

For each query, print the answer on a separate line.

Input copy	Output copy
6 3 1 2 1 3 3 4 3 5 5 6 1 2 3 2 2 5 2 2 2 5 5	2 3 -1