Practise Dynamic Forest offline queries
A. Dynamic get_path
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$$$ vertices, initially without edges.

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

  • link $$$u$$$ $$$v$$$ — add a new undirected edge between $$$u$$$ and $$$v$$$.
  • cut $$$i$$$ — cut the edge that was added during the $$$i$$$-th query.
  • get_path $$$u$$$ $$$v$$$ — find the length of the path $$$u \leftrightarrow v$$$.

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, get_path}) — the type of the query.

If $$$type$$$ is link, then two integers $$$u,v$$$ ($$$1 \le u,v \le n$$$) follow, meaning that a new undirected edge between $$$u$$$ and $$$v$$$ is added.

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 get_path, then two integers $$$u,v$$$ ($$$1 \le u,v \le n$$$) follow — the endpoints of a queried path.

Output

For each of the queries of type get_path, output the length of the path if it exists; otherwise, output $$$-1$$$.

Example
Input
9 12
link 1 2
link 2 3
get_path 1 3
cut 2
get_path 1 3
link 8 7
link 8 9
link 2 8
get_path 9 3
get_path 9 2
link 3 1
get_path 9 3
Output
2
-1
-1
2
4

B. Aquapark Graph
time limit per test
7 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You have a dynamic graph on $$$n$$$ vertices. The graph is described by an array $$$a$$$: vertex $$$i$$$ has an edge to $$$a_i$$$. Initially, $$$a_i=i$$$ for all $$$i$$$.

You are given $$$q$$$ triples ($$$u$$$,$$$x$$$,$$$s$$$). For each of them, do the following:

  • $$$a_u=x$$$ (delete the old edge $$$u \rightarrow a_u$$$ and add a new edge $$$u \rightarrow a_u=x$$$)
  • Start a new walk from vertex $$$s$$$. We walk along directed edges. After each move, we check whether we have visited this vertex earlier in the same walk; if so, we stop. Find the number of steps we took.
Input

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

Each of the following $$$q$$$ lines contains three integers $$$u,x,s$$$ ($$$1 \le u,x,s \le n$$$) — parameters of a query.

Output

For each query, output a single integer — the number of steps of the walk.

Example
Input
8 7
1 2 2
2 3 1
3 1 1
1 7 1
7 2 1
5 3 5
6 2 6
Output
1
3
3
2
4
5
5

C. Dynamic lca
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$$$ vertices, initially without edges.

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

  • link $$$u$$$ $$$v$$$ — add a new undirected edge between $$$u$$$ and $$$v$$$.
  • cut $$$i$$$ — cut the edge that was added during the $$$i$$$-th query.
  • lca $$$u$$$ $$$v$$$ $$$r$$$ — find the lowest common ancestor of $$$u$$$ and $$$v$$$ if we root their tree at $$$r$$$.

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, lca}) — the type of the query.

If $$$type$$$ is link, then two integers $$$u,v$$$ ($$$1 \le u,v \le n$$$) follow, meaning that a new undirected edge between $$$u$$$ and $$$v$$$ is added.

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 lca, then three integers $$$u,v,r$$$ ($$$1 \le u,v,r \le n$$$) follow — the two vertices and the root.

Output

For each of the queries of type lca, output the lowest common ancestor if $$$u,v,r$$$ are from the same tree; otherwise, output $$$-1$$$.

Example
Input
9 16
link 1 2
link 1 3
link 2 5
link 5 4
link 5 6
link 7 2
link 8 6
link 9 2
lca 8 9 4
lca 8 9 5
lca 8 9 1
cut 3
link 6 7
lca 8 9 4
lca 8 9 5
lca 8 9 1
Output
5
5
2
6
6
2

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