Two Trees#401

Two Trees

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:

Input

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.

Output

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.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

Let be the number of queries of the second type.

  1. ( points): n \le 16, q \le 16;

  2. ( points): n \le 16, q \le 2 \cdot 10^5;

  3. ( points): n \le 2000, q \le 2 \cdot 10^5,k \le 5;

  4. ( points): n \le 2000, q \le 2000;

  5. ( points): n \le 2 \cdot 10^5, q \le 2 \cdot 10^5, k \le 5;

  6. ( 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;

  7. ( points): no additional restrictions.