Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black. HW characters from A_{11} to A_{HW} represent the colors of the squares. A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

• Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed. The initial grid has at least one black square.

Constraints

• 1 \leq H,W \leq 1000
• A_{ij} is # or ..
• The given grid has at least one black square.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3

Problem Statement

We have a rectangular grid of squares with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left. On this grid, there is a piece, which is initially placed at square (s_r,s_c).

Takahashi and Aoki will play a game, where each player has a string of length N. Takahashi's string is S, and Aoki's string is T. S and T both consist of four kinds of letters: L, R, U and D.

The game consists of N steps. The i-th step proceeds as follows:

• First, Takahashi performs a move. He either moves the piece in the direction of S_i, or does not move the piece.
• Second, Aoki performs a move. He either moves the piece in the direction of T_i, or does not move the piece.

Here, to move the piece in the direction of L, R, U and D, is to move the piece from square (r,c) to square (r,c-1), (r,c+1), (r-1,c) and (r+1,c), respectively. If the destination square does not exist, the piece is removed from the grid, and the game ends, even if less than N steps are done.

Takahashi wants to remove the piece from the grid in one of the N steps. Aoki, on the other hand, wants to finish the N steps with the piece remaining on the grid. Determine if the piece will remain on the grid at the end of the game when both players play optimally.

Constraints

• 2 \leq H,W \leq 2 \times 10^5
• 2 \leq N \leq 2 \times 10^5
• 1 \leq s_r \leq H
• 1 \leq s_c \leq W
• |S|=|T|=N
• S and T consists of the four kinds of letters L, R, U and D.

Sample Input 1

2 3 3
2 2
RRL
LUD

Sample Output 1

YES

Here is one possible progress of the game:

• Takahashi moves the piece right. The piece is now at (2,3).
• Aoki moves the piece left. The piece is now at (2,2).
• Takahashi does not move the piece. The piece remains at (2,2).
• Aoki moves the piece up. The piece is now at (1,2).
• Takahashi moves the piece left. The piece is now at (1,1).
• Aoki does not move the piece. The piece remains at (1,1).

Sample Input 2

4 3 5
2 2
UDRRR
LLDUD

Sample Output 2

NO

Sample Input 3

5 6 11
2 1
RLDRRUDDLRL
URRDRLLDLRD

Sample Output 3

NO

Problem Statement

Takahashi and Aoki will play a game on a tree. The tree has N vertices numbered 1 to N, and the i-th of the N-1 edges connects Vertex a_i and Vertex b_i.

At the beginning of the game, each vertex contains a coin. Starting from Takahashi, he and Aoki will alternately perform the following operation:

• Choose a vertex v that contains one or more coins, and remove all the coins from v.
• Then, move each coin remaining on the tree to the vertex that is nearest to v among the adjacent vertices of the coin's current vertex.

The player who becomes unable to play, loses the game. That is, the player who takes his turn when there is no coin remaining on the tree, loses the game. Determine the winner of the game when both players play optimally.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq a_i, b_i \leq N
• a_i \neq b_i
• The graph given as input is a tree.

Sample Input 1

3
1 2
2 3

Sample Output 1

First

Here is one possible progress of the game:

• Takahashi removes the coin from Vertex 1. Now, Vertex 1 and Vertex 2 contain one coin each.
• Aoki removes the coin from Vertex 2. Now, Vertex 2 contains one coin.
• Takahashi removes the coin from Vertex 2. Now, there is no coin remaining on the tree.
• Aoki takes his turn when there is no coin on the tree and loses.

Sample Input 2

6
1 2
2 3
2 4
4 6
5 6

Sample Output 2

Second

Sample Input 3

7
1 7
7 4
3 4
7 5
6 3
2 1

Sample Output 3

First

Problem Statement

Note the unusual memory limit.

For a rectangular grid where each square is painted white or black, we define its complexity as follows:

• If all the squares are black or all the squares are white, the complexity is 0.
• Otherwise, divide the grid into two subgrids by a line parallel to one of the sides of the grid, and let c_1 and c_2 be the complexities of the subgrids. There can be multiple ways to perform the division, and let m be the minimum value of \max(c_1, c_2) in those divisions. The complexity of the grid is m+1.

You are given a grid with H horizontal rows and W vertical columns where each square is painted white or black. HW characters from A_{11} to A_{HW} represent the colors of the squares. A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

Find the complexity of the given grid.

Constraints

• 1 \leq H,W \leq 185
• A_{ij} is # or ..

Sample Input 1

3 3
...
.##
.##

Sample Output 1

2

Let us divide the grid by the boundary line between the first and second columns. The subgrid consisting of the first column has the complexity of 0, and the subgrid consisting of the second and third columns has the complexity of 1, so the whole grid has the complexity of at most 2.

Sample Input 2

6 7
.####.#
#....#.
#....#.
#....#.
.####.#
#....##

Sample Output 2

4

Problem Statement

Consider a circle whose perimeter is divided by N points into N arcs of equal length, and each of the arcs is painted red or blue. Such a circle is said to generate a string S from every point when the following condition is satisfied:

• We will arbitrarily choose one of the N points on the perimeter and place a piece on it.
• Then, we will perform the following move M times: move the piece clockwise or counter-clockwise to an adjacent point.
• Here, whatever point we choose initially, it is always possible to move the piece so that the color of the i-th arc the piece goes along is S_i, by properly deciding the directions of the moves.

Assume that, if S_i is R, it represents red; if S_i is B, it represents blue. Note that the directions of the moves can be decided separately for each choice of the initial point.

You are given a string S of length M consisting of R and B. Out of the 2^N ways to paint each of the arcs red or blue in a circle whose perimeter is divided into N arcs of equal length, find the number of ways resulting in a circle that generates S from every point, modulo 10^9+7.

Note that the rotations of the same coloring are also distinguished.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• |S|=M
• S_i is R or B.

Sample Input 1

4 7
RBRRBRR

Sample Output 1

2

The condition is satisfied only if the arcs are alternately painted red and blue, so the answer here is 2.

Sample Input 2

3 3
BBB

Sample Output 2

4

Sample Input 3

12 10
RRRRBRRRRB

Sample Output 3

78

Problem Statement

You are given a tree T with N vertices and an undirected graph G with N vertices and M edges. The vertices of each graph are numbered 1 to N. The i-th of the N-1 edges in T connects Vertex a_i and Vertex b_i, and the j-th of the M edges in G connects Vertex c_j and Vertex d_j.

Consider adding edges to G by repeatedly performing the following operation:

• Choose three integers a, b and c such that G has an edge connecting Vertex a and b and an edge connecting Vertex b and c but not an edge connecting Vertex a and c. If there is a simple path in T that contains all three of Vertex a, b and c in some order, add an edge in G connecting Vertex a and c.

Print the number of edges in G when no more edge can be added. It can be shown that this number does not depend on the choices made in the operation.

Constraints

• 2 \leq N \leq 2000
• 1 \leq M \leq 2000
• 1 \leq a_i, b_i \leq N
• a_i \neq b_i
• 1 \leq c_j, d_j \leq N
• c_j \neq d_j
• G does not contain multiple edges.
• T is a tree.

Sample Input 1

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

Sample Output 1

6

We can have at most six edges in G by adding edges as follows:

• Let (a,b,c)=(1,5,4) and add an edge connecting Vertex 1 and 4.
• Let (a,b,c)=(1,5,2) and add an edge connecting Vertex 1 and 2.
• Let (a,b,c)=(2,1,4) and add an edge connecting Vertex 2 and 4.

Sample Input 2

7 5
1 5
1 4
1 7
1 2
2 6
6 3
2 5
1 3
1 6
4 6
4 7

Sample Output 2

11

Sample Input 3

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

Sample Output 3

27