How far from the exterior? Take a 2D region of space divided into axis aligned unit square elements with their centers aligned at integer intervals. An edge is said to be internal if it is shared by two elements, otherwise it is an external edge.

Your goal is to find the minimum number of neighboring elements which must be traversed to reach an exterior edge starting from the center of each element, known as the traversal distance, or distance for short. You may only traverse through an edge (i.e. no corner cutting/diagonal movement). Note that "exterior elements" (elements which have at least one external edge) are considered to need to traverse 0 neighboring elements to reach an exterior edge..

Input

The input is a list of non-negative integer pair coordinates denoting the (x,y) of the center of all elements. It is assumed there are no overlapping elements (i.e. an x/y pair uniquely identifies an element).
You may not assume anything about the element input order.

You are welcome to transform the origin of the input to any location (e.g. 0,0 or 1,1, etc.).

You may assume that all input elements are connected, or in other words it is possible to travel from any one element to any other element using the rules above. Note that this does not mean that the 2D region is simply connected; it may have holes inside of it.

Example: the following is an invalid input.

0,0
2,0




error checking is not required.

The input may be from any source (file, stdio, function parameter, etc.)

Output

The output should be a list of coordinates identifying each element, and the corresponding integer distance traversed to get to an edge. The output may be in any element order desired (e.g. you need not output elements in the same order received as inputs).

The output may be to any source (file, stdio, function return value, etc.)

Any output which matches the coordinate of the element with it's exterior distance is fine, e.g. all of these are fine:

x,y: distance
...

[((x,y), distance), ...]

[(x,y,distance), ...]


Examples

Text example inputs are in the form x,y, with one element per line; you are welcome to reshape this into a convenient input format (see input format rules).

Text example outputs are in the format x,y: distance, with one element per line; again, you are welcome to reshape this into a convenient ouput format (see output format rules).

Graphical figures have the lower-left bound as (0,0), and the numbers inside represent the expected minimum distance traveled to reach an exterior edge. Note that these figures are purely for demonstration purposes only; your program does not need to output these.

Example 1

input:

1,0
3,0
0,1
1,2
1,1
2,1
4,3
3,1
2,2
2,3
3,2
3,3


Output:

1,0: 0
3,0: 0
0,1: 0
1,2: 0
1,1: 1
2,1: 0
4,3: 0
3,1: 0
2,2: 1
2,3: 0
3,2: 0
3,3: 0


graphical representation:



Example 2

input:

4,0
1,1
3,1
4,1
5,1
6,1
0,2
1,2
2,2
3,2
4,2
5,2
6,2
7,2
1,3
2,3
3,3
4,3
5,3
6,3
7,3
8,3
2,4
3,4
4,4
5,4
6,4
3,5
4,5
5,5


output:

4,0: 0
1,1: 0
3,1: 0
4,1: 1
5,1: 0
6,1: 0
0,2: 0
1,2: 1
2,2: 0
3,2: 1
4,2: 2
5,2: 1
6,2: 1
7,2: 0
1,3: 0
2,3: 1
3,3: 2
4,3: 2
5,3: 2
6,3: 1
7,3: 0
8,3: 0
2,4: 0
3,4: 1
4,4: 1
5,4: 1
6,4: 0
3,5: 0
4,5: 0
5,5: 0


graphical representation:



Example 3

input:

4,0
4,1
1,2
3,2
4,2
5,2
6,2
8,2
0,3
1,3
2,3
3,3
4,3
5,3
6,3
7,3
8,3
9,3
1,4
2,4
3,4
4,4
5,4
6,4
7,4
8,4
9,4
2,5
3,5
4,5
5,5
6,5
9,5
10,5
11,5
3,6
4,6
5,6
9,6
10,6
11,6
6,7
7,7
8,7
9,7
10,7
11,7


output:

4,0: 0
4,1: 0
1,2: 0
3,2: 0
4,2: 1
5,2: 0
6,2: 0
8,2: 0
0,3: 0
1,3: 1
2,3: 0
3,3: 1
4,3: 2
5,3: 1
6,3: 1
7,3: 0
8,3: 1
9,3: 0
1,4: 0
2,4: 1
3,4: 2
4,4: 2
5,4: 2
6,4: 1
7,4: 0
8,4: 0
9,4: 0
2,5: 0
3,5: 1
4,5: 1
5,5: 1
6,5: 0
9,5: 0
10,5: 0
11,5: 0
3,6: 0
4,6: 0
5,6: 0
9,6: 0
10,6: 1
11,6: 0
6,7: 0
7,7: 0
8,7: 0
9,7: 0
10,7: 0
11,7: 0


graphical representation:



Scoring

This is code golf. Shortest code in bytes wins. Standard loopholes apply. Any built-ins other than those specifically designed to solve this problem are allowed.
MATLAB/Octave, 143 bytes

function [v,x,y]=d(x,y)R=S=zeros(max(y+3),max(x+3));i=sub2ind(size(S),y+2,x+2);S(i)=1;while nnz(S=imerode(S,strel('disk',1,0)))R+=S;end;v=R(i);


Ungolfed

function [v,x,y]=d(x,y)
  R=S=zeros(max(y+3),max(x+3));
  i=sub2ind(size(S),y+2,x+2);
  S(i)=1;
  while nnz(S=imerode(S,strel('disk',1,0)))
    R+=S;
  end;
  v=R(i);


Explanation

Create Source and Result matrices of appropriate size, filled with zeros.

R=S=zeros(max(y+3),max(x+3));


Calculate the linear indices that correspond to the xy-pairs, with one element padding at the borders.

i=sub2ind(size(S),y+2,x+2);


Draw the structure.

S(i)=1;


S is shown here for Example 2:

0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   1   0   0   0   0   0
0   0   1   0   1   1   1   1   0   0   0
0   1   1   1   1   1   1   1   1   0   0
0   0   1   1   1   1   1   1   1   1   0
0   0   0   1   1   1   1   1   0   0   0
0   0   0   0   1   1   1   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0


Remove all border elements by image erosion

S=imerode(S,strel('disk',1,0))


using the structuring element disk with radius 1:

0   1   0
1   1   1
0   1   0


If diagonal movement was allowed, we would instead use the rectangle:

1   1   1
1   1   1
1   1   1


Then, increment the result for all non-border elements

R+=S;


and loop until the image is completely eroded.

while nnz(S)


Return the result for each xy-pair.

v=R(i);