Problem Statement

Takahashi is creating a program to analyze the structure of parentheses contained in mathematical expressions.

In mathematical expressions, parentheses are used to express the priority of calculations. Parentheses can be nested, and by including further parentheses within parentheses, complex calculation orders can be specified. Takahashi decided to first extract only the parentheses and examine the depth of their nesting.

You are given a string S consisting only of ( and ). Let N be the length of S, and number each character of the string from the beginning as the 1st, 2nd, \ldots, Nth character. The depth at the i-th character is defined as the number of ( minus the number of ) among all characters before the i-th character (that is, from the 1st to the (i-1)-th character). When i = 1, there are no characters before it, so the depth is 0.

For example, the depth of each character in ((())) is, from left to right, 0, 1, 2, 3, 2, 1. For the 4th character ), all 3 characters before it are (, so the depth is 3 - 0 = 3. The maximum depth in this string is 3. Also, the depth of each character in (()()) is, from left to right, 0, 1, 2, 1, 2, 1, and the maximum depth is 2.

Given the string S, find the maximum value among the depths of all characters in S.

Constraints

• 2 \leq N \leq 10^6 (N is the length of string S)
• S consists only of ( and )
• S is a correctly matched parenthesis sequence. That is, it satisfies both of the following conditions:
• At any position from the beginning, the number of ( is at least the number of )
• In the entire string, the number of ( and ) are equal

Sample Input 1

((()))

Sample Output 1

3

Sample Input 2

(()(())(()))

Sample Output 2

3

Sample Input 3

((((()))))((()))(())()(((((())))))

Sample Output 3

6

Problem Statement

Takahashi recorded a melody consisting of N notes as a string S.

The i-th character S_i of S is an uppercase English letter (A–Z), representing the i-th note.

For a string X, the compressed sequence of X is defined as follows.

Scan the characters of X from the beginning: always keep the first character, and for each subsequent character, keep it only if it differs from the last kept character. The resulting string is called the compressed sequence of X.

In a compressed sequence, any two adjacent characters are distinct.

For example, the compressed sequence of AAABBBAA is ABA, and the compressed sequence of ABCABC is ABCABC.

For a pair of integers (l, r) satisfying 1 \le l \le r \le N, consider the compressed sequence of the contiguous substring S_l S_{l+1} \dots S_r of S.

If the length of this compressed sequence is exactly 3 and its 1st and 3rd characters are equal, then the interval [l, r] is called a sandwich interval.

For example, if the contiguous substring corresponding to some interval is AABBA, its compressed sequence is ABA, which has length 3 and equal 1st and 3rd characters, so this interval is a sandwich interval.

On the other hand, if the contiguous substring is ABC, its compressed sequence is ABC, which has length 3 but the 1st and 3rd characters differ, so it is not a sandwich interval.

Also, if the contiguous substring is ABAB, its compressed sequence is ABAB, which has length 4, so it is not a sandwich interval.

Find the number of sandwich intervals.

Constraints

• 1 \le N \le 10^6
• S is a string of length N consisting of uppercase English letters (A–Z).

Sample Input 1

5
AABBA

Sample Output 1

2

Sample Input 2

3
ABC

Sample Output 2

0

Sample Input 3

25
AAABBAAAACCCAABBBADDDDAAA

Sample Output 3

25

Sample Input 4

75
AAAAABBBBAAAAAACCCDDDDDCCCCEEFFFFFFFEEEEEGGGGGGHHHGGGGIIIIIJJJJIIIIIIIKKKKK

Sample Output 4

111

Sample Input 5

1
A

Sample Output 5

0

Problem Statement

Takahashi is working part-time at a moving company. Today's job is to load N packages lined up in a row in a warehouse onto a truck. The weight of the i-th package from the left is W_i kg.

The truck has as many platforms as needed. When distributing the packages onto the platforms, Takahashi follows the following rule.

Rule:

Divide the row of N packages into groups of one or more consecutive packages with no gaps, and load each group onto exactly one platform. That is, each package is loaded onto exactly one platform, and packages loaded onto the same platform are consecutive in the original row. Furthermore, the total weight of packages on every platform must be equal.

Takahashi wants to use as many platforms as possible (because the more platforms there are, the lighter each platform's load becomes, making loading and unloading easier).

Find the maximum number of platforms that can be used when distributing the packages according to the above rule.

Note that using just one platform and loading all packages onto it always satisfies the rule, so a valid distribution always exists.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq W_i \leq 10^9
• All inputs are integers

Sample Input 1

6
1 2 3 3 2 1

Sample Output 1

4

Sample Input 2

10
2 4 2 2 6 4 2 2 8 8

Sample Output 2

5

Sample Input 3

15
1000000000 1000000000 1000000000 500000000 500000000 1000000000 1000000000 500000000 500000000 1000000000 1000000000 1000000000 500000000 500000000 1000000000

Sample Output 3

12

Problem Statement

Takahashi is trying to make a delivery by moving through a town.

The town has N locations numbered from 1 to N, and M roads connecting pairs of locations. The i-th road bidirectionally connects location U_i and location V_i, and it takes C_i time to traverse.

Takahashi is currently at location S. The package he wants to deliver is placed at location G, and the destination is location T.

Takahashi must first go to location G to pick up the package, and then deliver it to location T. During his travel, he may pass through the same location or the same road multiple times.

Find the minimum time required for Takahashi to start from location S, pass through location G, and reach location T. If it is impossible to reach location G from location S, or impossible to reach location T from location G, output -1.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq M \leq 1.5 \times 10^5
• 1 \leq S, G, T \leq N
• S, G, T are all distinct
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i
• 1 \leq C_i \leq 10^9
• There is at most one road connecting any pair of locations (there do not exist distinct i, j such that (U_i, V_i) and (U_j, V_j) are the same pair regardless of order)
• All input values are integers

Sample Input 1

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

Sample Output 1

8

Sample Input 2

5 2 1 3 5
1 2 4
3 4 7

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

14

Sample Input 4

12 18 2 9 12
1 2 5
1 3 2
2 4 4
3 4 1
3 5 7
4 6 3
5 6 2
6 7 4
7 8 6
8 9 1
6 9 10
4 10 8
10 11 2
11 12 3
9 12 5
5 10 1
2 5 9
7 11 2

Sample Output 4

22

Sample Input 5

3 2 1 2 3
1 2 1000000000
2 3 1000000000

Sample Output 5

2000000000

Problem Statement

Takahashi is the network administrator of a university campus. The campus has N buildings and M corridors, and each building is numbered from 1 to N. The i-th corridor bidirectionally connects building u_i and building v_i.

The buildings on this campus are classified into two types: "educational buildings" and "research buildings," and every corridor connects buildings of different types. In other words, the graph consisting of buildings and corridors is a bipartite graph. However, which type each building belongs to is not given in the input. Also, the graph is not necessarily connected.

According to university policy, Wi-Fi should be available on all corridors. When a Wi-Fi access point is installed in a building, Wi-Fi becomes available on all corridors that have that building as an endpoint.

Takahashi wants to achieve a state where, for every corridor, at least one of the two buildings at its endpoints has an access point installed. Find the minimum number of buildings that need to be selected to satisfy this condition.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq M \leq 10^5
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i (no self-loops)
• There is at most one corridor connecting the same pair of buildings (no multi-edges)
• The given graph is a bipartite graph
• The graph is not necessarily connected
• All input values are integers

Sample Input 1

4 4
1 2
2 3
3 4
4 1

Sample Output 1

2

Sample Input 2

5 4
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

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

Sample Output 3

5

Sample Input 4

8 16
1 5
1 6
1 7
1 8
2 5
2 6
2 7
2 8
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8

Sample Output 4

4

Sample Input 5

1 0

Sample Output 5

0