Problem Statement

You are given a positive integer N and two strings S and T, each of length N and consisting of lowercase English letters.

Find the Hamming distance between S and T. That is, find the number of integers i such that 1 \leq i \leq N and the i-th character of S is different from the i-th character of T.

Constraints

• 1\leq N \leq 100
• N is an integer.
• Each of S and T is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcarc
agcahc

Sample Output 1

2

S and T differ in the 2nd and 5th characters, but not in other characters. Thus, the answer is 2.

Sample Input 2

7
atcoder
contest

Sample Output 2

7

Sample Input 3

8
chokudai
chokudai

Sample Output 3

0

Sample Input 4

10
vexknuampx
vzxikuamlx

Sample Output 4

4

Problem Statement

N people labeled from 1 to N participated in a certain contest. The score of person i (1 \leq i \leq N) was P_i.

In this contest, the rank of each of the N people is determined by the following procedure:

1. Prepare a variable r, and initialize r = 1. Initially, the ranks of the N people are all undetermined.
2. Repeat the following operation until the ranks of all N people are determined:
   • Let x be the maximum score among the people whose ranks are currently undetermined, and let k be the number of people whose score is x. Determine the rank of those k people with score x to be r, and then add k to r.

Print the rank of each of the N people.

Constraints

• 1\leq N \leq 100
• 1\leq P_i \leq 100
• All input values are integers.

Sample Input 1

4
3 12 9 9

Sample Output 1

4
1
2
2

The ranks of the N\ (=4) people are determined as follows:

1. Prepare a variable r and initialize r=1. At first, the ranks of all 4 people are undetermined.
2. Currently, persons 1, 2, 3, 4 have undetermined ranks. The maximum score among them is P_2\ (=12). Therefore, determine the rank of person 2 to be r\ (=1), and then add 1 to r, making r=2.
3. Currently, persons 1, 3, 4 have undetermined ranks. The maximum score among them is P_3=P_4\ (=9). Therefore, determine the ranks of persons 3 and 4 to be r\ (=2), and then add 2 to r, making r=4.
4. Currently, person 1 has an undetermined rank. The maximum score among them is P_1\ (=3). Therefore, determine the rank of person 1 to be r\ (=4), and then add 1 to r, making r=5.
5. The ranks of all 4 people are now determined, so the process ends.

Sample Input 2

3
3 9 6

Sample Output 2

3
1
2

Sample Input 3

4
100 100 100 100

Sample Output 3

1
1
1
1

Sample Input 4

8
87 87 87 88 41 38 41 38

Sample Output 4

2
2
2
1
5
7
5
7

Problem Statement

You are given a simple undirected graph with N vertices and M edges, where the vertices are labeled 1 to N. The i-th edge connects vertices u_i and v_i.
What is the minimum number of edges that need to be deleted from this graph so that the graph becomes a forest?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \left( \frac{N(N-1)}{2}, 2 \times 10^5\right)
• 1 \leq u_i < v_i \leq N
• The given graph is simple.
• All input values are integers.

Sample Input 1

4 4
1 2
1 3
2 4
3 4

Sample Output 1

1

For example, if you delete the first edge, the graph becomes a forest.

Sample Input 2

5 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

2

Problem Statement

N couples are seated in a line.
Count the number of pairs of couples such that neither couple was originally sitting next to each other, and both couples can end up sitting next to each other by swapping seats among those four people.

There is a sequence A = (A_1, A_2, \dots, A_{2N}) of length 2N. Each of the integers 1, 2, \dots, N appears exactly twice in A.

Find the number of integer pairs (a, b) satisfying 1 \leq a < b \leq N and all of the following conditions:

• The two occurrences of a in A are not adjacent.
• The two occurrences of b in A are not adjacent.
• By performing the following operation one or more times in any order, it is possible to reach a state where the two occurrences of a in A are adjacent and the two occurrences of b in A are also adjacent.
  • Choose an integer pair (i, j) (1 \leq i \leq 2N, 1 \leq j \leq 2N) such that A_i = a and A_j = b, and swap A_i with A_j.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• Each of 1, 2, \dots, N appears exactly twice in A.
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
3
1 2 3 3 1 2
4
1 1 2 2 3 3 4 4
5
1 2 3 4 5 1 2 3 4 5

Sample Output 1

1
0
4

Consider the first test case.
(a, b) = (1, 2) satisfies the conditions in the problem statement, for the following reasons:

• The two occurrences of 1 in A are not adjacent.
• The two occurrences of 2 in A are not adjacent.
• By performing the operation where (i, j) = (1, 6) and swapping A_1 with A_6, you can reach a state where the two occurrences of 1 are adjacent and the two occurrences of 2 are also adjacent.

(1, 2) is the only pair (a, b) that satisfies the conditions.

Problem Statement

You are given a positive integer N and two strings S and T, each of length N and consisting of lowercase English letters.

Determine whether it is possible to make S identical to T by repeating the operation below any number of times (possibly zero). If it is possible, also find the minimum number of operations required.

• Choose two lowercase English letters x, y and replace every occurrence of x in S with y.

Constraints

• 1\leq N \leq 2\times 10^5
• N is an integer.
• Each of S and T is a string of length N, consisting of lowercase English letters.

Sample Input 1

6
afbfda
bkckbb

Sample Output 1

4

By performing the operation four times in the following way, you can make S identical to T:

1. Choose x= b and y= c. S becomes afcfda.
2. Choose x= a and y= b. S becomes bfcfdb.
3. Choose x= f and y= k. S becomes bkckdb.
4. Choose x= d and y= b. S becomes bkckbb, which is identical to T.

It cannot be done with fewer than four operations, so the minimum number of operations required is 4.

Sample Input 2

4
abac
abac

Sample Output 2

0

S and T are already identical, so no operations are required.

Sample Input 3

4
abac
abrc

Sample Output 3

-1

No matter how you repeat the operation, it is impossible to make S identical to T.

Sample Input 4

4
abac
bcba

Sample Output 4

4

Problem Statement

You are given positive integers N, K, and an integer sequence of length N: A = (A_1, A_2, \dots, A_N).

Find \displaystyle \sum_{1\leq l\leq r\leq N} \Bigg(\sum_{l\leq i\leq r} A_i\Bigg)^K, modulo 998244353.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq K \leq 10
• 0 \leq A_i < 998244353
• All input values are integers.

Sample Input 1

3 2
3 1 2

Sample Output 1

75

The value is A_1^2+A_2^2+A_3^2+(A_1+A_2)^2+(A_2+A_3)^2+(A_1+A_2+A_3)^2=3^2+1^2+2^2+4^2+3^2+6^2=75.

Sample Input 2

1 10
0

Sample Output 2

0

Sample Input 3

10 5
91 59 85 60 57 72 12 3 27 16

Sample Output 3

428633385

Be sure to find the sum modulo 998244353.

Problem Statement

You are given a connected undirected graph with N vertices and M edges, where the vertices are labeled 1 to N. The graph does not contain self-loops, but it may contain multi-edges. Each edge has a color, and the i-th edge has a color c_i (1 \leq c_i \leq C) and connects vertices u_i and v_i. Also, a sequence A = (A_1, A_2, \dots, A_C) is given.

Among the spanning trees of this graph, those satisfying the following condition are called colorful spanning trees:

• For every integer i such that 1 \leq i \leq C, the number of edges of color i included in the spanning tree is at most A_i.

Find the number of integer pairs (L, R) with 1 \leq L \leq R \leq C that satisfy the following condition:

• There exists a colorful spanning tree T such that every edge in T has a color c with L \leq c \leq R.

Constraints

• 2 \leq N \leq 150
• N - 1 \leq M \leq \min\left(\frac{C N (N-1)}{2}, 5 \times 10^5\right)
• 1 \leq C \leq 300
• 1 \leq A_i \leq N-1
• \sum_{i=1}^C A_i \leq 300
• 1 \leq u_i < v_i \leq N
• 1 \leq c_i \leq C
• If i \neq j, then (u_i, v_i, c_i) \neq (u_j, v_j, c_j)
• The given graph is connected.
• All input values are integers.

Sample Input 1

3 4 3
1 2 1
1 2 1
1 2 2
1 3 3
2 3 2

Sample Output 1

4

For example, (L, R) = (1, 2) satisfies the condition, because the spanning tree T formed by the 1st and 4th edges is a colorful spanning tree, and all edges in T have colors c with 1 \leq c \leq 2.
There are four pairs (L, R) that satisfy the condition: (1, 2), (1, 3), (2, 2), (2, 3).

Sample Input 2

5 10 6
2 2 4 1 1 1
1 3 2
1 5 4
2 3 3
1 4 1
4 5 1
4 5 3
2 4 1
1 4 3
1 3 4
1 2 5

Sample Output 2

11

Sample Input 3

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

Sample Output 3

2