E. DequeQL
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the modern world there are many different databases based on various structures and principles. In addition to relational (e.g., MySQL) and graph (e.g., GraphQL) databases, a recent intern at VK company proposed the idea of a new database called DequeQL based on deques. Of course not all intern ideas are really good, but being a responsible mentor, Lev decided to implement his idea and test its efficiency.

A deque is a data structure that stores a sequence of elements and allows adding a new element or removing an element from either end of the sequence. The basic data block in DequeQL is called a unit — an empty deque representing the minimal block of information. The database itself consists of a set of numbered deques nested within each other. A deque that is not nested within any other is called a root. Of course, if a unit is not contained within another deque, it is also considered a root.

DequeQL supports four modification operations:

  1. push_back($$$d_1$$$, $$$d_2$$$) — place the root $$$d_1$$$ at the end of the root $$$d_2$$$ ($$$d_1$$$ ceases to be a root);
  2. push_front($$$d_1$$$, $$$d_2$$$) — place the root $$$d_1$$$ at the beginning of the root $$$d_2$$$ ($$$d_1$$$ ceases to be a root);
  3. pop_back($$$d$$$) — extract the last element from the root $$$d$$$ (this element becomes a root);
  4. pop_front($$$d$$$) — extract the first element from the root $$$d$$$ (the extracted element also becomes a root);

Note that operations can only be performed on root elements of the database. Lev has already implemented these operations and decided that DequeQL could be useful in one of the new VK projects if its functionality is expanded to include support for answering the pop_complexity($$$d$$$) query: what is the minimum number of pop_back or pop_front operations needed to make $$$d$$$ a root? The structure of the database itself does not change, so there is no need to perform the corresponding pop actions.

While Lev is on vacation you have the opportunity to prove yourself as a qualified developer. You are given a database consisting of $$$n$$$ units numbered from $$$1$$$ to $$$n$$$. Implement the required functionality and output the answer to each query.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ — the number of units in the database and the number of queries ($$$1 \le n, m \le 2 \cdot 10^5$$$).

The $$$i$$$-th of the following lines contains the $$$i$$$-th query in the format "<command> $$$d$$$" or "<command> $$$d_1$$$ $$$d_2$$$" where <command> is the command or query described in the statement ($$$1 \le d, d_1, d_2 \le n$$$). It is guaranteed that database modification operations are only performed on root vertices, and that pop operations are only performed on non-empty deques.

Output

For each query, output the answer on a separate line — the minimum number of pop operations required to make the corresponding element a root.

Scoring

Points for each subtask are awarded only if all tests of this subtask and the required subtasks are successfully passed.

SubtaskPointsConstraints Required Subtasks Testing Feedback
0–examples from the statementfull
18$$$n, m \le 10$$$0full
29each deque directly contains no more than two elementsfirst error
313each deque directly contains no more than three elements2first error
412$$$n, m \le 2000$$$0, 1first error
520all pop_complexity queries come after modification operationsfirst error
614no pop operationsfirst error
724none0 – 6first error
Example
Input
6 11
push_back 2 1
push_front 3 1
pop_back 1
push_back 4 2
push_front 6 5
push_front 2 1
push_back 5 1
pop_complexity 3
pop_complexity 4
pop_complexity 5
pop_complexity 6
Output
2
2
1
2