提示: 欢迎访问OurACM平台。
Problem 1985 LCP Problem

Accept: 47    Submit: 175
Time Limit: 1000 mSec    Memory Limit : 60000 KB

Problem Description

LCP (Longest Common Prefix), is defined as the longest common prefix of two strings. For example, LCP (“AC”, “ACOrz”) = “AC”, LCP (“WA”,”AC”) = “”.

Now you are given several DNA sequence. (Only contains ‘A’, ‘T’, ‘C’ and ‘G’).

You are expected to output the length of the LCP of two DNA sequence.

Input

In the first line there is an integer T, indicates the number of test cases. (T <= 10)

In each case, the first line contains only one integer n, indicates the number of DNA sequence. (1 <= n <=100000, the number of letters in one test case is smaller than 100000)

Then one integer m, then m lines, each line contains two integers a,b ,indicates the index of the two DNA sequence. (0 <= m <= 100000, 0<= a,b <n)

Output

For each case, output “Case idx: “first where idx is the case index start from 1 in a single line , then output m lines indicate the length of the LCP.

Sample Input

2 2 ATCG AT 1 0 1 3 AT ATT ATTT 3 0 0 0 1 0 2

Sample Output

Case 1: 2 Case 2: 2 2 2

Source

FOJ有奖月赛-2010年11月

Submit  Back  Status  Discuss