The first thing we need to check is whether there is an empty place on any shelf. In case there isn't, we check whether all the books are in the right place. If they're not, no solution exists and we output -1, otherwise the solution is 0.

Let's see how to solve the test cases worth ~50\%~ of points in which for each book it holds that it is on the same shelf both in the beginning and in the end. We divide the shelves into three categories:

1. the shelf with an empty place in the beginning

   1. ~k~ - the number of books on the shelf
   2. ~lis~ - the longest subsequence of books that are in a good relative order in the beginning
   3. each book that isn't in ~lis~, we need to lift in order to arrange the books on that shelf, in other words, we need ~k-lis~ lifts
   4. let's notice that by pushing books we can free a position on the shelf where we need to place a book before we lift it
   5. ~lis~ is easily found in ~\mathcal O(k \log k)~ using the well-known algorithm for finding the longest increasing subsequence

2. the shelf is full, but all the books are in their place

   1. we don't need a single lift for shelves of this type

3. the shelf is full, but there is a book that is not in its place

   1. we move one book that isn't in ~lis~ over to an empty space on another shelf
   2. we arrange the other books on the shelf in the right order, not lifting the books contained in ~lis~
   3. we put the book we moved to another shelf to its right place
   4. for this type of shelf, we need ~k-lis+1~ lifts

As for test cases that have books that aren't on the same shelf in the beginning and in the end, we will split those shelves into two categories:

1. the shelves with books that are on that shelf both in the beginning and in the end and every book that is there in the end was also there in the beginning

   1. we solve these shelves in the same way we solved the shelves in test cases worth ~50\%~ of total points

2. other shelves

Now we are left with solving the second category of shelves. Let's build an undirected graph where the nodes are the shelves. Two nodes are connected if there is a book that is located on the shelf represented by the first node in the beginning, and in the end it's located on the shelf represented by the second node.

Let's solve each component of this graph separately and introduce two new cases:

1. all shelves in the component are full in the beginning

   1. let's now build a directed graph of this component so that we direct the edge from the node where the book is coming to (the node that the book is located in the end) to the node from where the book came from (the node that the book is located in the beginning)
   2. notice that each node will have the same indegree and outdegree and that we can build an Euler cycle
   3. we place a book from node ~A~ that is not on the same shelf in the beginning and in the end to an empty place on a shelf that has an available place in that moment
   4. we start from node ~A~ and move in an Euler cycle, when we go from node ~A~ to node ~B~, we move the book from node ~B~ to node ~A~
   5. during the Euler cycle traversal, in the moment when a shelf has an empty place, we place the books on that shelf that are there in the beginning and in the end in a good relative order - we do this in the way described in the first category of the solution for ~50\%~ of total points
   6. ~sum\_k~ - the number of books on shelves in that component
   7. ~sum\_lis~ - the sum of ~lis~ of individual shelves in that component
   8. we need ~sum\_k-sum\_lis+1~ lifts to solve this component
   9. notice that we don't need to build an Euler cycle because a reconstruction of the solution is not required

2. there is a shelf in the component that is not completely full in the beginning

   1. pick a node with a larger indegree than outdegree and a node that has a larger outdegree than indegree and add a dummy edge between these two nodes
   2. repeat this procedure until these types of nodes exist
   3. build an Euler cycle and start with the node with an empty place in the beginning, if we pass through a right edge, we move the book, if we pass through a dummy edge, nothing is moved
   4. it is important to notice that there will always be an empty place in the node where we are located in, even if we entered that node using a dummy edge; this holds because of the fact that if a shelf has a larger outdegree than indegree, then the number of available places in the beginning on that shelf is larger than or equal to the difference of outdegree and indegree
   5. we solve the books on the same shelf in the beginning and in the end in the same way as in the previous case
   6. we need ~sum\_k-sum\_lis~ lifts to solve this component

The total complexity of this algorithm is ~\mathcal O(NM \log M)~.