Problem Statement

You are given a string S consisting of uppercase English letters.

Output the string obtained by replacing every character in S other than A with ..

Constraints

• S is a string of length between 1 and 100 (inclusive) consisting of uppercase English letters.

Sample Input 1

ATCODER

Sample Output 1

A......

Since the first character is the only occurrence of A in S, output the string obtained by changing the second through seventh characters of S to ..

Sample Input 2

BANANA

Sample Output 2

.A.A.A

S may contain two or more occurrences of A.

Sample Input 3

CORRECT

Sample Output 3

.......

S may contain no occurrence of A.

Problem Statement

You are given two integers A and B, each between 0 and 9, inclusive.

Print any integer between 0 and 9, inclusive, that is not equal to A + B.

Constraints

• 0 \leq A \leq 9
• 0 \leq B \leq 9
• A + B \leq 9
• A and B are integers.

Sample Input 1

2 5

Sample Output 1

2

When A = 2, B = 5, we have A + B = 7. Thus, printing any of 0, 1, 2, 3, 4, 5, 6, 8, 9 is correct.

Sample Input 2

0 0

Sample Output 2

9

Sample Input 3

7 1

Sample Output 3

4

Problem Statement

N people numbered 1,2,\ldots,N were in M photos. In each of the photos, they stood in a single line. In the i-th photo, the j-th person from the left is person a_{i,j}.

Two people who did not stand next to each other in any of the photos may be in a bad mood.

How many pairs of people may be in a bad mood? Here, we do not distinguish a pair of person x and person y, and a pair of person y and person x.

Constraints

• 2 \leq N \leq 50
• 1 \leq M \leq 50
• 1 \leq a_{i,j} \leq N
• a_{i,1},\ldots,a_{i,N} contain each of 1,\ldots,N exactly once.
• All values in the input are integers.

Sample Input 1

4 2
1 2 3 4
4 3 1 2

Sample Output 1

2

The pair of person 1 and person 4, and the pair of person 2 and person 4, may be in a bad mood.

Sample Input 2

3 3
1 2 3
3 1 2
1 2 3

Sample Output 2

0

Sample Input 3

10 10
4 10 7 2 8 3 9 1 6 5
3 6 2 9 1 8 10 7 4 5
9 3 4 5 7 10 1 8 2 6
7 3 1 8 4 9 5 6 2 10
5 2 1 4 10 7 9 8 3 6
5 8 1 6 9 3 2 4 7 10
8 10 3 4 5 7 2 9 6 1
3 10 2 7 8 5 1 4 9 6
10 6 1 5 4 2 3 8 9 7
4 5 9 1 8 2 7 6 3 10

Sample Output 3

6

Problem Statement

You are given a tree with N vertices and N-1 edges.
The vertices are numbered 1,2,\ldots,N. The i-th edge connects Vertex a_i and Vertex b_i.

Determine whether this tree is a star.

Here, a star is a tree where there is a vertex directly connected to all other vertices.

Notes

For the definition of a tree, see Tree (graph theory) - Wikipedia.

Constraints

• 3 \leq N \leq 10^5
• 1 \leq a_i \lt b_i \leq N
• The given graph is a tree.

Sample Input 1

5
1 4
2 4
3 4
4 5

Sample Output 1

Yes

The given graph is a star.

Sample Input 2

4
2 4
1 4
2 3

Sample Output 2

No

The given graph is not a star.

Sample Input 3

10
9 10
3 10
4 10
8 10
1 10
2 10
7 10
6 10
5 10

Sample Output 3

Yes

Problem Statement

You are given a string S consisting of a, b, c.

Find the number of non-empty substrings of S in which no two adjacent characters are the same, modulo 998244353.

Two substrings are considered distinct if they are taken from different positions, even if they are identical as strings.

Constraints

• S is a string of length between 1 and 3 \times 10^5, inclusive, consisting of a, b, c.

Sample Input 1

abbc

Sample Output 1

6

The substrings in which no two adjacent characters are the same are the following six:

• a (from the 1st to the 1st character of S)
• b (from the 2nd to the 2nd character of S)
• b (from the 3rd to the 3rd character of S)
• c (from the 4th to the 4th character of S)
• ab (from the 1st to the 2nd character of S)
• bc (from the 3rd to the 4th character of S)

Note that, as with the 2nd and 3rd entries, two substrings are considered distinct if they are taken from different positions, even if they are identical as strings.

Sample Input 2

cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca

Sample Output 2

760

Problem Statement

You are given a string S of length N consisting only of lowercase English letters.

Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.

Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.

Constraints

• 2 \leq K \leq N \leq 10
• N and K are integers.
• S is a string of length N consisting only of lowercase English letters.

Sample Input 1

3 2
aab

Sample Output 1

1

The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.

Sample Input 2

5 3
zzyyx

Sample Output 2

16

There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.

Sample Input 3

10 5
abcwxyzyxw

Sample Output 3

440640

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

Find the maximum length of a subsequence B=(B_1,B_2,\ldots,B_{|B|}) of integer sequence A that satisfies the following condition.

• B_i+1=B_{i+1} for all integers i satisfying 1\le i\le |B| - 1.

Constraints

• 1\le N\le 2\times 10^5
• 1\le A_i\le 10^9
• All input values are integers.

Sample Input 1

7
3 4 3 5 7 6 2

Sample Output 1

4

B=(3,4,5,6) is a subsequence of A that satisfies the condition, and its length is 4.

There is no subsequence satisfying the condition with length greater than 4, so output 4.

Sample Input 2

5
5 4 3 2 1

Sample Output 2

1

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

10

Problem Statement

A country has N cities and M power plants, which we collectively call places.
The places are numbered 1,2,\dots,N+M, among which Places 1,2,\dots,N are the cities and Places N+1,N+2,\dots,N+M are the power plants.

This country has E power lines. Power Line i (1 \le i \le E) connects Place U_i and Place V_i bidirectionally.
A city is said to be electrified if one can reach at least one of the power plants from the city using some power lines.

Now, Q events will happen. In the i-th (1 \le i \le Q) event, Power Line X_i breaks, making it unusable. Once a power line breaks, it remains broken in the succeeding events.

Find the number of electrified cities right after each events.

Constraints

• All values in input are integers.
• 1 \le N,M
• N+M \le 2 \times 10^5
• 1 \le Q \le E \le 5 \times 10^5
• 1 \le U_i < V_i \le N+M
• If i \neq j, then U_i \neq U_j or V_i \neq V_j.
• 1 \le X_i \le E
• X_i are distinct.

Sample Input 1

5 5 10
2 3
4 10
5 10
6 9
2 9
4 8
1 7
3 6
8 10
1 8
6
3
5
8
10
2
7

Sample Output 1

4
4
2
2
2
1

Initially, all cities are electrified.

• The 1-st event breaks Power Line 3 that connects Point 5 and Point 10.
  • Now City 5 is no longer electrified, while 4 cities remain electrified.
• The 2-nd event breaks Power Line 5 that connects Point 2 and Point 9.
• The 3-rd event breaks Power Line 8 that connects Point 3 and Point 6.
  • Now Cities 2 and 3 are no longer electrified, while 2 cities remain electrified.
• The 4-th event breaks Power Line 10 that connects Point 1 and Point 8.
• The 5-th event breaks Power Line 2 that connects Point 4 and Point 10.
• The 6-th event breaks Power Line 7 that connects Point 1 and Point 7.
  • Now City 1 is no longer electrified, while 1 city remains electrified.

Problem Statement

Given is a string S. From this string, Takahashi will make a new string T as follows.

• First, mark one or more characters in S. Here, no two marked characters should be adjacent.
• Next, delete all unmarked characters.
• Finally, let T be the remaining string. Here, it is forbidden to change the order of the characters.

How many strings are there that can be obtained as T? Find the count modulo (10^9 + 7).

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abc

Sample Output 1

4

There are four strings that can be obtained as T: a, b, c, and ac.

Marking the first character of S yields a;

marking the second character of S yields b;

marking the third character of S yields c;

marking the first and third characters of S yields ac.

Note that it is forbidden to, for example, mark both the first and second characters.

Sample Input 2

aa

Sample Output 2

1

There is just one string that can be obtained as T, which is a. Note that marking different positions may result in the same string.

Sample Input 3

acba

Sample Output 3

6

There are six strings that can be obtained as T: a, b, c, aa, ab, and ca.

Sample Input 4

chokudai

Sample Output 4

54