1763: Cousins

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

Two strings

a

and

b

are defined to be

first cousins

if they can be made equal by removing no more than half the characters from each. For example "abcdef" and "axcyd" are first cousins because we can remove 3 of the 6 characters (b,e,f) from the first string and 2 of the 5 characters in the second string (x,y) resulting in "acd". Two strings

c

and

d

are said to be n+1

st cousins

if there exists a string

e

that is a first cousin of

c

and is an n

th

cousin of

d

.

Given two strings x and y, determine the smallest n ≥ 1 such that x is an nth cousin of y.

Input consists of several test cases. Each test case consists of two lines representing x and y. x and y each consist of at least 1 and at most 100 lower case letters. Two lines containing 0 follow the last test case. For each test case, output a line containing n or not related if x and y are not nth cousins for any n.

输入样例 复制

a
b
abb
baa
abcdef
axcyd
0
0

输出样例 复制

2
2
1