Linked List

Interview

Time limit1sMemory limit512 MB

Summary

Maintain a permutation of 1..N under slide(a,b) moves (move a to just after b), reporting how far a moves each time and printing the final list.

Level: Medium6 of 10
Topics: Linked list, Array, Simulation, Implementation
Solved: No attempts yet

Problem

A linked list is one basic linear data structure usually taught in any data structures course in college. Whatever its practicality (or impracticality) in real-life applications, it often serves to demonstrate a way to store data in non-contiguous storage.

Three common operations on a linked list are insertion, deletion, and searching. In this problem you deal with a fourth operation that may find a place in real-life applications, namely sliding. Suppose you are given a linked list of N integers linked sequentially from 1 to N (1 → 2 → 3 → ... → N). A slide operation takes two integers a and b, written slide(a, b), and moves integer a from its position to the position immediately to the right of b.

For example, let N = 5, so the initial linked list is 1 → 2 → 3 → 4 → 5. The operation slide(4, 1) changes the linked list into 1 → 4 → 2 → 3 → 5, that is, 4 is moved from its position to the position immediately to the right of 1. In this case 4 moves two positions to the left. If another operation, slide(1, 5), is then performed, the linked list becomes 4 → 2 → 3 → 5 → 1, that is, 1 is moved from its position to the position immediately to the right of 5. In this case 1 moves four positions to the right.

Given a linked list of N integers from 1 to N (all integers linked sequentially from 1 to N) and Q slide operations, perform the sliding operation for each slide(a, b) and output how far a moves in the linked list. If a moves to the left, output it as a negative value (for example, −2 above); otherwise output it as a non-negative value (for example, 4 above).

After all operations have been performed, output the final linked list as well.

Input

The input begins with two integers: N Q (1 ≤ N, Q ≤ 100000), the number of integers in the linked list and the number of operations, respectively. The next Q lines each contain two integers: a b (1 ≤ a, b ≤ N; a ≠ b), representing a slide(a, b) operation to be performed.

Output

For each operation, output on a line how far the corresponding integer moved. If the integer moved to the left, output the negative value; otherwise output the non-negative value. The last line contains N integers separated by a single space representing the linked list data after all operations have been performed.

Examples3

Example 1
Input
```
5 3
4 1
1 5
3 2
```
Expected output
```
-2
4
0
4 2 3 5 1
```
Example 2
Input
```
3 4
1 2
2 3
3 1
1 3
```
Expected output
```
1
2
0
1
3 1 2
```

Example 3

Input

10 2
2 7
10 7

Expected output

5
-3
1 3 4 5 6 7 10 2 8 9