Consider a graph whose vertices are integers and which has a directed edge \(u \to v\) if \(u\) can be transformed into \(v\), then the original problem is boiled down to a shortest path problem from Vertex \(1\) to Vertex \(N\) on the unweighted graph.
It is known that the shortest path on an unweighted graph can be obtained by Breadth-First Search (BFS). Especially in this problem, denoting by \(V\) the number of edges in the graph and \(E\) that of the edges,

• the number of the outgoing edge from a vertex is at most two, so \(\frac{V}{2} \leq E \leq V\);
• finding the vertices directly traversable from \(n\) requires an \(\mathrm{O}(\log n)\) complexity,

so the complexity is \(\mathrm{O}(M \log M)\) where \(M\) is the maximum index of vertices to be visited.

Thus the problem has been solved… wait, really? The issue remains in the number of vertices \(V\). Without any constraints, the number of vertices is \(\infty\), so the complexity is \(\mathrm{O}(\infty)\) as well. That’s why we need to somehow constrain the vertices to be visited.

Recall that we want to know the shortest path from \(1\) to \(N\); so we do not have to inspect the numbers that will not appear in the path from \(1\) to \(N\).
What is the maximum number appear in the path from \(1\) to \(N\)? This can be obtained through some observations.

Observation \(1\)

If the integer currently has \(A\) digits, then the number of digits after the operation will be greater than or equal to \(A\).

The first operation multiplies the integer on the blackboard by \(a\), enlarging the integer, so the number of digits will increase too, or remain the same.
The second operation just moves the tail of a string of length \(N\) to the head, which keeps the number of digits to \(A\).
Therefore, neither of operations makes the number of digits less than \(A\).

Observation \(2\)

During the operations of changing \(1\) to \(N\), the number of digits of the integer written on the blackboard will never exceed \(A\).

For example, when \(a = 5, N=52562\), the integer changes as

• \(1 \to 5\to 25\to 125\to 512\to 251\to 1255\to 5125\to 25625 \to 52562\),

where the sequence of numbers of digits are

• \(1\to 1\to 2\to 3\to 3\to 3\to 4\to 4\to 5 \to 5\);

none of them exceeds the number of digits of \(N\).

This cane be proved by Observation \(1\). By Observation \(1\), the sequence of numbers of digits is monotonically increasing, and its final value is \(A\), so every integer appear in the sequence of digit counts is less than or equal to \(A\).

By the two observations above, we now see that we only have to inspect the numbers whose number of digits is less than \(A\), where \(A\) denotes the number of digits of \(N\).

Therefore, denoting by \(M\) the maximum index of vertex on the graph that may be visited, \(M \lt 10N\) because \(10N\) is a \((A + 1)\)-digit number, so \(M = \mathrm{O}(N)\). Therefore the problem has been solved in a total of \(\mathrm{O}(N \log N)\) time. (Actually, the vertices actually visited during BFS is far less than \(M\), so the constant factor of the algorithm is quite light.)

Alternatively, one may reverse the order of edges and do BFS starting from \(N\) and ending at \(1\). The analysis above can be applied to this algorithm too; the problem can be solved in a total of \(\mathrm{O}(N \log N)\) time.

A sample code in a Python follows.

from collections import deque

a, N = map(int, input().split())

M = 1
while M <= N:
  M *= 10

d = [-1] * M
Q = deque()
d[1] = 0
Q.append(1)

while len(Q):
  c = Q.popleft()
  dc = d[c]

  op1 = a * c
  if op1 < M and d[op1] == -1:
    d[op1] = dc + 1
    Q.append(op1)

  if c >= 10 and c % 10 != 0:
    s = str(c)
    op2 = int(s[-1] + s[:-1])
    if op2 < M and d[op2] == -1:
      d[op2] = dc + 1
      Q.append(op2)

print(d[N])