You are given two equal undirected trees and consisting of vertices. Trees are equal if, for all pairs of vertices , the edge between G_u and G_v exists if and only if the edge between H_u and H_v exists.
Some vertices can be connected to their version in another tree with an undirected edge. Especially, a leaf vertex G_v can be connected to vertex H_v. Let us say that if leaf vertex G_v is connected to H_v directly, then vertex is enabled, and the vertex is disabled otherwise.
Initially, all leaf vertices are disabled. You are asked to handle the following queries:
— toggle the status of vertex , if is disabled then change its status to enabled and vice versa otherwise;
— print the length of the shortest path from vertex G_u to vertex H_v.
The first line contains two integers and (3 \le n \le 2 \cdot 10^5; 1 \le q \le 2 \cdot 10^5) — number of vertices and queries, respectively.
Each of the following n-1 lines contains two integers , (1 \le u,v \le n) — description of trees, edges (G_u;G_v) and (H_u;H_v).
Each of the following lines contains a description of queries. There are two possible query descriptions:
(1 \le v \le n) — toggle the status of vertex ;
(1 \le u,v \le n) — print the length of the shortest path from vertex G_u to H_v.
For each query of the second type, print a single integer in a single line — the length of the shortest path between given vertices. If there is no such path, print -1.
Example 1
Example 2
Let be the number of queries of the second type.
( points): n \le 16, q \le 16;
( points): n \le 16, q \le 2 \cdot 10^5;
( points): n \le 2000, q \le 2 \cdot 10^5,k \le 5;
( points): n \le 2000, q \le 2000;
( points): n \le 2 \cdot 10^5, q \le 2 \cdot 10^5, k \le 5;
( points): n \le 2 \cdot 10^5, q \le 2 \cdot 10^5, there is no query of first type after query of second type;
( points): no additional restrictions.