Longest Identical Substring After Character Replacements

You are given a string s and a sequence of queries. Each query consists of two characters c1 and c2. For each query, replace all occurrences of c1 in s with c2, and then compute the length of the longest substring in s that contains only one unique, repeated character.

The task is to process the queries in order. After each query, print the length of the longest contiguous segment where all characters are identical.

Mathematical Formulation:

Let \( s \) be a string of length \( n \). For each query \( (c_1, c_2) \), update \( s \) as follows: \[ s \leftarrow \text{replace}(s, c_1, c_2) \quad \text{where} \quad \text{replace}(s, c_1, c_2) = \{ x : x = c_2 \text{ if } x = c_1 \text{ else } x \} \] and find: \[ L = \max_{1 \leq i \leq n}\{ \ell \mid s_i = s_{i+1} = \cdots = s_{i+\ell-1} \} \] Output \( L \) after each query.

Examples:

Input:
abbac
3
a b
b c
c a
Output:
4
5
5
Explanation:
After 1st query, "abbac" becomes "bbbac" and the longest identical substring is "bbbb" (of length 4).
After 2nd query, the string becomes "cccac" yielding a longest substring of "ccccc" (length 5).
After 3rd query, the string becomes "aaaac" with the longest substring still of length 5.

</p>

inputFormat

The input is given from stdin and has the following format:

<string s>
<integer Q>
<c1_1> <c2_1>
<c1_2> <c2_2>
...
<c1_Q> <c2_Q>

Here, s is the initial string, Q is the number of queries, and each of the next Q lines contains two characters separated by space representing the query.

outputFormat

For each query, output one integer on a new line indicating the length of the longest contiguous substring composed of identical characters after applying that query.

## sample

abbac
3
a b
b c
c a

4
5
5

</p>