#212623. [UTS 2024] 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 and exists if and only if the edge between and exists.

Some vertices can be connected to their version in another tree with an undirected edge. Especially, a leaf vertex can be connected to vertex . Let us say that if leaf vertex is connected to 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 to vertex .

The first line contains two integers and (; ) --- number of vertices and queries, respectively.

Each of the following lines contains two integers , --- description of trees, edges and .

Each of the following lines contains a description of queries. There are two possible query descriptions:

• --- toggle the status of vertex ;
• --- print the length of the shortest path from vertex to .

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

7 11
1 2
2 3
1 4
2 5
4 6
4 7
1 6
1 3
2 1 6
2 1 2
1 7
2 5 4
2 6 3
1 6
1 3
1 5
2 6 3

样例输出 1

2
3
5
4
6

样例输入 2

3 2
1 2
1 3
1 3
2 1 2

样例输出 2

3

Let be the number of queries of the second type.

• ( points): , ;
• ( points): , ;
• ( points): , ;
• ( points): , ;
• ( points): , ;
• ( points): , , there is no query of first type after query of second type;
• ( points): no additional restrictions.