Tests Renumeration
Contest: Технокубок 2018 - Отборочный Раунд 1
Difficulty rating: 2200
Tags: greedy, implementation

The All-Berland National Olympiad in Informatics has just ended! Now Vladimir wants to upload the contest from the Olympiad as a gym to a popular Codehorses website.

Unfortunately, the archive with Olympiad's data is a mess. For example, the files with tests are named arbitrary without any logic.

Vladimir wants to rename the files with tests so that their names are distinct integers starting from 1 without any gaps, namely, "1", "2", ..., "n', where n is the total number of tests.

Some of the files contain tests from statements (examples), while others contain regular tests. It is possible that there are no examples, and it is possible that all tests are examples. Vladimir wants to rename the files so that the examples are the first several tests, all all the next files contain regular tests only.

The only operation Vladimir can perform is the "move" command. Vladimir wants to write a script file, each of the lines in which is "move file_1 file_2", that means that the file "file_1" is to be renamed to "file_2". If there is a file "file_2" at the moment of this line being run, then this file is to be rewritten. After the line "move file_1 file_2" the file "file_1" doesn't exist, but there is a file "file_2" with content equal to the content of "file_1" before the "move" command.

Help Vladimir to write the script file with the minimum possible number of lines so that after this script is run:

- all examples are the first several tests having filenames "1", "2", ..., "e", where e is the total number of examples;
- all other files contain regular tests with filenames "e + 1", "e + 2", ..., "n", where n is the total number of all tests.

Input format:
The first line contains single integer n (1 ≤ n ≤ 105) — the number of files with tests.

n lines follow, each describing a file with test. Each line has a form of "name_i type_i", where "name_i" is the filename, and "type_i" equals "1", if the i-th file contains an example test, and "0" if it contains a regular test. Filenames of each file are strings of digits and small English letters with length from 1 to 6 characters. The filenames are guaranteed to be distinct.

Output format:
In the first line print the minimum number of lines in Vladimir's script file.

After that print the script file, each line should be "move file_1 file_2", where "file_1" is an existing at the moment of this line being run filename, and "file_2" — is a string of digits and small English letters with length from 1 to 6.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5
01 0
2 1
2extra 0
3 1
99 0

Example output:
4
move 3 1
move 01 5
move 2extra 4
move 99 3

Example input:
2
1 0
2 1

Example output:
3
move 1 3
move 2 1
move 3 2

Editorial:
Firstly we will get rid of all tests that are already named correctly. After this, let's call samples "tests of 1 type", and system tests "tests of 2 type".
Let's denote "free positions" such indices $$i \ ( i \in [ 1.. n ] )$$ such that there is currently no test with the name i. If there are no any free positions, then we can't rename each test using only one operation move because firstly we have to make its index a free position.
Let's show that one free position is always enough. If there is one, then let's put some test of the corresponding type which has wrong name (a name that doesn't coincide with its type) into this position. It is clear that there will be at least one such test — otherwise all tests of corresponding type are at their positions, and there is no free position of this type. Then there are two cases — either we free a correct position (then we will have another free position) or we move a test which had illegal name (so we don't create any free positions).
It's better to move a test which occupies some position so we will have a new free position after it. It is clear that when there are no tests such that their names are correct numbers, but they are in position of different type, then we can't keep the quantity of free positions as it is, and after moving any test this quantity will decrease.
This approach is optimal because we will have to perform either cnt (cnt is the number of tests that aren't correctly named initially) or cnt + 1 operations. cnt + 1 will be the answer only if we have to make an operation that will create a free position (if there are no free positions initially).
This number of operations is optimal because if we have cnt incorrectly named tests, then we can't rename them in less than cnt operations; and this is possible only if we have at least one free position initially; otherwise we have to free some position.