INVESORT - Inversion Sort

#ifdef LOCAL
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <queue>
#include <unordered_map>
#include <cstring>
#include <map>
#else
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#endif

#ifndef LOCAL
#define endl '\n'
#endif

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define fi first
#define se second

#define YES cout << "YES" << endl
#define NO cout << "NO" << endl

#define lsb(x) (x & (-x))
#define popcount(x) __builtin_popcount(x)

using namespace std;

#define double long double

typedef long long ll;
typedef pair<int, int> pii;

const int INF = 1e9+5;

int n = 10;
char a[15], b[15];
unordered_map<string, int> d;

void read() {
    cin >> a >> b;
    if (a[0] == '*') exit(0);
}

// Am precalculat distantele de la "abcdefghej"
void bfs(string s) {
    queue<string> q;
    d[s] = 1;
    q.push(s);
    while (!q.empty()) {
        s = q.front();
        int dist = d[s];
        q.pop();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                reverse(s.begin() + i, s.begin() + j + 1);
                if (d[s] == 0) {
                    d[s] = dist + 1;
                    q.push(s);
                }
                reverse(s.begin() + i, s.begin() + j + 1);
            }
        }
    }
}

int solve() {
    string s(n, 'a');
    char c = 'a';
    // Am transformat sirul b a.i. dist(a, b) = dist("abcdefghij", b')
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            if (a[i] == b[j])
                s[j] = c++;
    }
    return d[s] - 1; // Distanta de la b' la "abcdefghij"
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    bfs("abcdefghij");
    while (true)  {
        read();
        cout << solve() << endl;
    }
    return 0;
}