No submission language available for this problem.

Background

泛洪算法，以及获得路线练习。为了方便练习，数据保证路线的唯一性。

Description

有一个字符矩阵，. 表示可以行走，# 表示障碍，无法行走。先要求从左上角 (1, 1) 走到右下角 (n, m) 的最短的步数，以及最短的一条行走路线。

模板题，因此数据保证唯一性

Format

Input

第一行两个整数 n, m 表示 n 行 m 列

之后有 n 行每行 m 个字符输入.

Output

第一行一个整数表示最少的步数。

第二行输出从 (1,1) 开始到达 (n,m) 的一条最短路线。每两个位置之间用一个空格隔开。

Samples

7 10
......#...
...##...#.
.#......#.
.######.#.
.#......#.
.##.#.###.
....#.....

17
(1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (2,6) (2,7) (2,8) (1,8) (1,9) (1,10) (2,10) (3,10) (4,10) (5,10) (6,10) (7,10)

Limitation

n,m ≤ 100