D1. Dynamic Xenia
time limit per test
7 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a forest on $$$n$$$ blue vertices, initially without edges.

You are also given $$$q$$$ queries of six types:

  • link $$$u$$$ $$$v$$$ $$$w$$$ — add a new undirected edge between $$$u$$$ and $$$v$$$ with weight $$$w$$$.
  • cut $$$i$$$ — cut the edge that was added during the $$$i$$$-th query.
  • make_blue $$$u$$$ — color $$$u$$$ blue.
  • make_red $$$u$$$ — color $$$u$$$ red.
  • get_blue $$$u$$$ — find the shortest path from $$$u$$$ to a blue vertex.
  • get_red $$$u$$$ — find the shortest path from $$$u$$$ to a red vertex.

It is guaranteed that integers $$$i$$$ are distinct and that the graph remains a forest.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n,q \le 2\cdot 10^5$$$) — the number of vertices and the number of queries, respectively.

The $$$j$$$-th of the following $$$q$$$ lines describes a query according to the following principle:

First, a single string $$$type$$$ is given ($$$type \in$$$ {link, cut, make_blue, make_red, get_blue, get_red}) — the type of the query.

If $$$type$$$ is link, then three integers $$$u,v,w$$$ ($$$1 \le u,v \le n$$$, $$$1 \le w \le 10^9$$$) follow, meaning that a new undirected edge with weight $$$w$$$ is added between $$$u$$$ and $$$v$$$.

If $$$type$$$ is cut, then a single integer $$$i$$$ ($$$1 \le i \lt j \le q$$$) follows — the index of the query that added the edge that is required to be removed.

If $$$type$$$ is make_blue, then a single integer $$$u$$$ ($$$1 \le u \le n$$$) follows — the vertex to be colored blue.

If $$$type$$$ is make_red, then a single integer $$$u$$$ ($$$1 \le u \le n$$$) follows — the vertex to be colored red.

If $$$type$$$ is get_blue, then a single integer $$$u$$$ ($$$1 \le u \le n$$$) follows — the vertex to find the shortest path to a blue vertex from.

If $$$type$$$ is get_red, then a single integer $$$u$$$ ($$$1 \le u \le n$$$) follows — the vertex to find the shortest path to a red vertex from.

Output

For each of the queries of type get_blue or get_red, output the length of the shortest path from $$$u$$$ to a blue or a red vertex, respectively.

Example
Input
9 19
link 1 2 1
link 1 3 1
link 2 5 3
link 5 4 1
link 5 6 1
link 7 2 1
link 8 6 1
link 9 2 1
make_red 3
get_red 8
make_red 7
get_red 8
cut 3
get_red 5
make_red 4
make_red 6
get_blue 5
make_red 5
get_blue 5
Output
7
6
-1
0
2