#P2133. 天作之合

天作之合

题目背景

生活就是一次A*,你是我的第一个目标状态。——小明

题目描述

在小明的学校中,一共有若干个女生。小明认为每个女生的特征可以抽象为一个6位的数字串其中不重复地包含1~6这6个数码。

在小明心中,有一个理想的女生,她的特征数字串为A。如果串Y是串X交换两个连续的数码所得,那么我们认为特征数字串X和Y相似。首先,小明找到了他的同桌,她的特征数字串为S。每次,小明会寻找一个特征数字串和当前串相似的女生,直到寻找到适合他的(即特征数字串和A相同或相似的)。定义每个女生的合适程度为找到此人至少需要找女生的数量(包括他的同桌和此人自己)。显然,合适程度数值越小的女生越适合小明。

然而,小明觉得老天不会轻易地让他找到,所以他认为合适程度第二小的才是他最合适的伴侣(也就是小红)。那么,请你帮他写一个程序,求出对于小明,小红的合适程度是多少。

输入格式

第1行,一个特征数字串A。

第2行,一个特征数字串S。

输出格式

一行,一个正整数表示小红的合适程度。

123654
123456
3

提示

对于全部数据,保证串A和S合法,且保证能找到。

数据比较弱。