Pegman

Time limit5sMemory limit512 MB

Summary
Find the fewest arrow direction changes so a walker starting from any cell never leaves the grid, or report that it is impossible.
Level

Medium5 of 10

Topics
Greedy, Simulation
Solved
No attempts yet

Problem

If you have used Google Street View, you have probably picked up the Pegman icon and dropped it on the map. Today a mischievous user is going to drop Pegman on one cell of a grid with RR rows and CC columns. Each cell of the grid is either blank or holds an arrow pointing up, right, down, or left.

If the cell where Pegman lands is blank, he stands still forever. If it holds an arrow, he starts walking in that direction. While he walks, a blank cell leaves his direction unchanged, and another arrow turns him to the direction of that arrow before he keeps walking.

Pegman may walk around inside the grid forever, but he may also walk off the edge of the grid. You can prevent that by changing the direction of one or more arrows. An arrow can only be changed to one of the other three directions, and no arrow can be added or erased.

What is the smallest number of arrows you must change so that Pegman never walks off the edge, no matter which cell he is dropped on?

Input

The first line has the number of test cases TT. The first line of each test case has two space-separated integers RR and CC. The next RR lines each hold CC characters, and each character describes one cell:

  • . period: no arrow
  • ^ caret: up arrow
  • > greater than: right arrow
  • v lowercase v: down arrow
  • < less than: left arrow

Limits

  • 1≤T≤1001 \le T \le 100
  • 1≤R,C≤1001 \le R, C \le 100

Output

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1 and y is the minimum number of arrows whose direction must change so that Pegman never leaves the grid, wherever he is dropped. If no number of changes achieves this, print IMPOSSIBLE in place of y.

Explanation

In the first test case of the first example, Pegman walks off the top edge wherever he is dropped. Changing the upper arrow to point down prevents it, because he then walks back and forth between the two arrows forever.

In the second test case, he walks clockwise around the grid forever wherever he is dropped. No arrow has to change.

In the third test case, the user can drop Pegman on the up arrow in the middle, and he walks off the top edge. Changing that arrow does not help, because he would only leave through a different edge.

In the fourth test case, the only cell he can be dropped on is blank, so he stands still.

Examples2

  1. Example 1

    Input
    4
2 1
^
^
2 2
>v
^<
3 3
...
.^.
...
1 1
.
    Expected output
    Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 0

  2. Example 2

    Input
    5
1 1
^
1 1
>
1 1
v
1 1
<
1 1
.
    Expected output
    Case #1: IMPOSSIBLE
Case #2: IMPOSSIBLE
Case #3: IMPOSSIBLE
Case #4: IMPOSSIBLE
Case #5: 0