Description

Given a n×m grid maze which consists of walls (#), floors (.), start (A), and end(B). You can walk in four directions: up, down, left and right, but you cannot pass the walls. Please output a path to walk from the start to the end with minimum steps, or it is impossible to go from the start to the end.

Input

The first line contains two integers n and m, being the number of rows and columns of the grid maze.

The following n lines describes the maze. Each line has m characters which is one of #, ., A, or B.

There is exactly one A and B in the input.

Restrictions

• 1 ≤  n, m  ≤ 1000

Output

If it is possible to go from the start to the end, print "YES" in the first line, the number of minimum steps in the second line.

If it is impossible, please print "NO" in the first line.

Remember there should be a ‘\n’ at the end of the last line of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In graph theory, a directed acyclic graph (DAG) is a directed graph with no directed cycles.

Given a directed graph G = (V, E), note that:
- For any two vertices u, v in V, there may not exists path from u to v.
- G doesn't have multiple edges and self-loops.

V is a set of n vertices, denoted by 1, 2, ..., n.

E is a set of m edges, and each edge is represented by two ordered vertices u, v, which denotes an edge from vertex u to vertex v.

Please answer if graph G is a directed acyclic graph (DAG) or not.

Input

The first line contains two integers n and m — the size of V and the size of E.

Each of the following m lines contains two integers u_i and v_i, being an edge in E.

Restrictions

- 2 ≤ n ≤ 10⁵
- 1 ≤ m ≤ min(n * (n - 1) / 2, 2 * 10⁵)
- 1 ≤ u_i, v_i ≤ n, u_i ≠ v_i for 1 ≤ i ≤ m

Output

Output one line.

If graph G is DAG, output "YES". Otherwise, output "NO".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given an n×m grid, where each cell contains a positive integer. The integer at row i and column j is denoted as Ai,j​. You can start your walk from any cell in the grid and move in four cardinal directions: up, down, left, and right. However, there is a restriction on the movement: you can only move to a neighboring cell if its integer value is strictly smaller than the integer value of the cell you are currently standing on.

Input

• The first line contains two integers n and m, being the number of rows and columns of the grid maze.
• This is followed by n lines, each containing m integers, representing the grid values. The j-th integer in the i-th line represents Ai,j​.

Restrictions

For test 1 ~ 4

• n = 1
• 1 ≤ m ≤ 1000
• 1 ≤ A_i,j ≤ 100000

For test 5 ~ 10

• 1 ≤ n, m ≤ 1000
• 1 ≤ A_i,j ≤ 100000

Output

output a single integer, the length of the longest path you can traverse starting from any cell and following the movement constraints.

Remember there should be a ‘\n’ at the end of the last line of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given the postorder and inorder traversal of a binary tree. Your job is to reconstruct the tree and print the preorder traversal of the tree.

Note

• Each vertex of the tree is labeled 1 ~ n distinctly.

Input

Each input is given in three lines.

The first line contains an integer n: The number of vertices of the binary tree.

The second line is the postorder traversal of the tree.

The last line is the inorder traversal of the tree.

Note

• For both traversals, each vertex is seperated by an empty space.

Restriction

• 1 ≤ n ≤ 2∗10⁵

Output

Output should be printed in one line. Containing the preorder traversal of the tree. Each vertex of the traversal should be seperated with an empty space.

Remember to print a ‘\n’ at the end of the output.

Do not include any spaces at the "end of line".

Sample Input  Download

Sample Output  Download

Tags

Discuss