384. Country

Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Once upon a time in a faraway kingdom there was a very wise King. This King wanted to improve the road system of the country. For the purposes of this problem the road system can be considered as an undirected graph without loops and parallel edges (the vertices of this graph correspond to the cities and the edges correspond to the roads). The King was fond of mathematics, so he reformed the road system of the kingdom in the following mathematical way: for each two distinct cities there was exactly one common neighbour (any city is not neighbour of itself). The road reform was successful, but with the lapse of time some roads were destroyed. The government of the kingdom wants to know the distances between cities at any moment of time. Your task is to help the government with this problem.

Input
The first line of the input contains two integer numbers n and m — the number of cities and the number of roads immediately after the reform (). The next m lines describe the roads of the kingdom. Each of these lines contains two integer numbers xi and yi — 1-based indices of cities connected by this road. The following lines describe queries of the government and information about road destruction. If the line describes a destruction of the road, it will be formatted as "DELETE x", where x is 1-based index of the road. Otherwise it will be formated as "LENGTH x y", where x and y are 1-based indices of cities. The queries will appear in the input till the end of the file. The total number of queries doesn't exceed .

Output
For each "
LENGTH
" query output the answer on the separate line, or -1 if there's no way to travel from one city to another.

Example(s)
sample input
sample output
3 3
1 2
2 3
3 1
LENGTH 1 2
DELETE 1
LENGTH 1 2
LENGTH 2 3
DELETE 3
LENGTH 1 2
1
2
1
-1




Online Contester Team © 2002 - 2010. All rights reserved.