아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Find and Replace

면접 대비

시간 제한2초메모리 제한1024 MB

요약
길이가 같은 두 문자열이 주어질 때, 한 글자를 다른 글자로 모두 바꾸는 연산으로 입력을 출력으로 만드는 최소 횟수를 구하고 불가능하면 -1을 출력한다.
난이도

보통10점 중 6점

유형
그래프, 유니온 파인드, 구현
정답자
아직 제출이 없습니다

문제

Bessie is using the latest and greatest innovation in text-editing software, miV! She starts with an input string consisting solely of upper and lowercase English letters and wishes to transform it into some output string. With just one keystroke, miV allows her to replace all occurrences of one English letter c_1c\_1 in the string with another English letter c_2c\_2. For example, given the string aAbBa, if Bessie selects c_1c\_1 as 'a' and c_2c\_2 as 'B', the given string transforms into BAbBB.

Bessie is a busy cow, so for each of TT (1≤T≤101\le T\le 10) independent test cases, output the minimum number of keystrokes required to transform her input string into her desired output string.

입력

The first line contains TT, the number of independent test cases.

The following TT pairs of lines contain an input and output string of equal length. All characters are upper or lowercase English letters (either A through Z or a through z). The sum of the lengths of all strings does not exceed 10510^5.

출력

For each test case, output the minimum number of keystrokes required to change the input string into the output string, or −1-1 if it is impossible to do so.

힌트

The first input string is the same as its output string, so no keystrokes are required.

The second input string cannot be changed into its output string because Bessie cannot change one 'B' to 'A' while keeping the other as 'B'.

The third input string can be changed into its output string by changing 'a' to 'b'.

The last input string can be changed into its output string like so: ABCD →\rightarrow EBCD →\rightarrow EACD →\rightarrow BACD.

예제1

  1. 예제 1

    입력
    4
    abc
    abc
    BBC
    ABC
    abc
    bbc
    ABCD
    BACD
    
    예상 출력
    0
    -1
    1
    3