Problem:


Problem D: Off Balance

You are working for an administration office of the International
Center for Picassonian Cubism (ICPC), which plans to build a new art
gallery for young artists.  The center is organizing an architectural
design competition to find the best design for the new building.

Submitted designs will look like a screenshot of a well known
game as shown below.

This is because the center specifies that 
the building should be constructed by stacking regular units
called pieces, each of which consists of four cubic blocks.
In addition, the center requires the competitors to submit designs
that satisfy the following restrictions.

All the pieces are aligned.  When two pieces touch each other, the faces of
the touching blocks must be placed exactly at the same position.

All the pieces are stable.  Since pieces are merely stacked, 
their centers of masses must be carefully positioned so as not to 
collapse.

The pieces are stacked in a tree-like form 
in order to symbolize boundless potentiality of young artists.
In other words, one and only one
piece touches the ground, and each of other pieces touches one and
only one piece on its bottom faces.

The building has a flat shape.
  This is because the construction site
  is a narrow area located between a
  straight moat and an expressway where 
  no more than one block can be placed 
   between the moat and the
expressway as illustrated below.

It will take many days to fully check stability of designs as it requires 
complicated structural calculation.
Therefore, you are
asked to quickly check obviously unstable designs by focusing on 
centers of masses.  The rules of your quick check are as follows.

 Assume the center of mass of a block is located at the center of the
block, and all blocks have the same weight.  
We denote a location of a block by xy-coordinates of its
left-bottom corner.  The unit length is the edge length of a block.

 
Among the blocks of the piece that touch another piece or the ground on their
bottom faces, let xL be the leftmost x-coordinate of 
the leftmost block, and let xR be the rightmost
x-coordinate of the rightmost block.
Let the x-coordinate of its accumulated center of mass of
the piece be M, where the accumulated center of mass of a piece P
is the center of the mass of the pieces that are directly and indirectly 
supported by P, in addition to P itself.  Then the piece is
stable, if and only if
xL < M < xR.  Otherwise, it is
unstable.  A design of a building is unstable if any of its pieces is unstable.

Note that the above rules could  judge some designs to be unstable even 
if it would not collapse in reality.  For example, the left one of the
following designs shall be judged to be unstable.

Also note that the rules judge boundary cases to be unstable.  For example, the top piece in the above right design has its center of mass exactly above the right end of the bottom piece.  This shall be judged to be unstable.

Write a program that judges stability of each design based on the above quick check rules.

Input

The input is a sequence of datasets.  The end of the input is
indicated by a line containing two zeros separated by a space.  Each
dataset, which represents a front view of a building, is formatted as follows.

w h			

p0(h-1)p1(h-1)...p(w-1)(h-1)	

...		 	     

p01p11...p(w-1)1	

p00p10...p(w-1)0	

The integers w and h separated by a space are the numbers of columns
and rows of the layout, respectively.  You may assume 1 ≤ w ≤
10 and 1 ≤ h ≤ 60.  The next h lines specify the placement of
the pieces.  The character pxy indicates the status of a block at
(x,y), either `.', meaning empty, or one digit character between
`1' and `9', inclusive, meaning a block of a piece.  
(As mentioned earlier, we denote a location of a block by xy-coordinates of its
left-bottom corner.)

When two blocks with the same number touch each other by any of their
top, bottom, left or right face, those blocks are of the same piece.
(Note that there might be two different pieces that are denoted by 
the same number.)
The bottom of a block at (x,0) touches the ground.

You may assume that the pieces in each dataset are stacked in a tree-like form.

Output

For each dataset, output a line containing a word STABLE
when the design is stable with respect to the above quick check rules.
Otherwise, output UNSTABLE.  The output
should be written with uppercase letters, and should not contain any other extra characters.

Sample Input

4 5
..33
..33
2222
..1.
.111
5 7
....1
.1..1
.1..1
11..1
.2222
..111
...1.
3 6
.3.
233
23.
22.
.11
.11
4 3
2222
..11
..11
4 5
.3..
33..
322.
2211
.11.
3 3
222
2.1
111
3 4
11.
11.
.2.
222
3 4
.11
.11
.2.
222
2 7
11
.1
21
22
23
.3
33
2 3
1.
11
.1
0 0

Output for the Sample Input

STABLE
STABLE
STABLE
UNSTABLE
STABLE
STABLE
UNSTABLE
UNSTABLE
UNSTABLE
UNSTABLE



Sample input:
4 5
..33
..33
2222
..1.
.111
5 7
....1
.1..1
.1..1
11..1
.2222
..111
...1.
3 6
.3.
233
23.
22.
.11
.11
4 3
2222
..11
..11
4 5
.3..
33..
322.
2211
.11.
3 3
222
2.1
111
3 4
11.
11.
.2.
222
3 4
.11
.11
.2.
222
2 7
11
.1
21
22
23
.3
33
2 3
1.
11
.1
0 0


Sample output:
STABLE
STABLE
STABLE
UNSTABLE
STABLE
STABLE
UNSTABLE
UNSTABLE
UNSTABLE
UNSTABLE

Submission status: Accepted

Solution code:
from collections import deque
dd = [(-1, 0), (0, -1), (1, 0), (0, 1)]
while 1:
    w, h = map(int, raw_input().split())
    if w == h == 0:
        break
    P = [list(raw_input()) for i in xrange(h)]
    L = [[None]*w for i in xrange(h)]

    deq = deque()
    cnt = 0
    g = []; XL = []; XR = []; M = []; C = []
    for i in xrange(h):
        for j in xrange(w):
            if P[i][j] is '.':
                continue
            if L[i][j] is None:
                p = P[i][j]
                deq.append((j, i))
                L[i][j] = cnt
                if i == h-1 or p != P[i+1][j] != '.':
                    xl = xr = j
                else:
                    xl = w; xr = -1;
                s = 2 + j
                while deq:
                    x, y = deq.popleft()
                    for dx, dy in dd:
                        nx = x + dx; ny = y + dy
                        if 0 <= nx < w and 0 <= ny < h and p == P[ny][nx] and L[ny][nx] is None:
                            deq.append((nx, ny))
                            L[ny][nx] = cnt
                            s += nx
                            if ny == h-1 or p != P[ny+1][nx] != '.':
                                xl = min(xl, nx); xr = max(xr, nx)
                cnt += 1
                g.append(set()); M.append(s); C.append(4); XL.append(xl); XR.append(xr+1)
            if i:
                if L[i][j] != L[i-1][j] != None and L[i-1][j] not in g[L[i][j]]:
                    g[L[i][j]].add(L[i-1][j])
                    M[L[i][j]] += M[L[i-1][j]]
                    C[L[i][j]] += C[L[i-1][j]]
    for i in xrange(cnt):
        if not XL[i]*C[i] < M[i] < XR[i]*C[i]:
            print "UNSTABLE"
            break
    else:
        print "STABLE"

Submission status: Accepted

Solution code:
#2006_D
"""
import sys
from collections import defaultdict
def dfs(d,y,x,f):
    global ans
    if d >= 10:
        return
    f_ = defaultdict(int)
    for i in f.keys():
        f_[i] = f[i]
    for t,s in vr[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if s == x+1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t,s-1,f_)
            f_[(t,s)] = 1
            break

    for t,s in vl[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if s == x-1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t,s+1,f_)
            f_[(t,s)] = 1
            break

    for t,s in vd[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if t == y+1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t-1,s,f_)
            f_[(t,s)] = 1
            break

    for t,s in vu[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if t == y-1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t+1,s,f_)
            f_[(t,s)] = 1
            break
    return
while 1:
    w,h = map(int, sys.stdin.readline()[:-1].split())
    if w == h == 0:
        break
    a = [list(map(int, sys.stdin.readline()[:-1].split())) for i in range(h)]
    vr = defaultdict(list)
    vl = defaultdict(list)
    vd = defaultdict(list)
    vu = defaultdict(list)
    f = defaultdict(int)
    for y in range(h):
        for x in range(w):
            if a[y][x] == 1:
                f[(y,x)] = 1
            if a[y][x] in [1,3]:
                for x_ in range(x):
                    vr[(y,x_)].append((y,x))
            elif a[y][x] == 2:
                sy,sx = y,x
    for y in range(h):
        for x in range(w)[::-1]:
            if a[y][x] in (1,3):
                for x_ in range(x+1,w):
                    vl[(y,x_)].append((y,x))
    for x in range(w):
        for y in range(h):
            if a[y][x] in (1,3):
                for y_ in range(y):
                    vd[(y_,x)].append((y,x))
    for x in range(w):
        for y in range(h)[::-1]:
            if a[y][x] in (1,3):
                for y_ in range(y+1,h):
                    vu[(y_,x)].append((y,x))
    ind = [[[0]*4 for i in range(w)] for j in range(h)]
    ans = 11
    dfs(0,sy,sx,f)
    ans = ans if ans < 11 else -1
    print(ans)
"""

#2018_D
"""
import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)

def dfs(d,s,l,v,dic):
    s_ = tuple(s)
    if dic[(d,s_)] != None:
        return dic[(d,s_)]
    if d == l:
        dic[(d,s_)] = 1
        for x in s:
            if x > (n>>1):
                dic[(d,s_)] = 0
                return 0
        return 1
    else:
        res = 0
        i,j = v[d]
        if s[i] < (n>>1):
            s[i] += 1
            res += dfs(d+1,s,l,v,dic)
            s[i] -= 1
        if s[j] < (n>>1):
            s[j] += 1
            res += dfs(d+1,s,l,v,dic)
            s[j] -= 1
        dic[(d,s_)] = res
        return res

def solve(n):
    dic = defaultdict(lambda : None)
    m = int(sys.stdin.readline())
    s = [0]*n
    f = [[1]*n for i in range(n)]
    for i in range(n):
        f[i][i] = 0
    for i in range(m):
        x,y = [int(x) for x in sys.stdin.readline().split()]
        x -= 1
        y -= 1
        s[x] += 1
        f[x][y] = 0
        f[y][x] = 0
    v = []
    for i in range(n):
        for j in range(i+1,n):
            if f[i][j]:
                v.append((i,j))
    l = len(v)
    print(dfs(0,s,l,v,dic))

while 1:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    solve(n)
"""
#2011_D
"""
import sys
def dfs(s,d,f,v):
    global ans
    if ans == n-n%2:
        return
    if d > ans:
        ans = d
    for i in range(n):
        if s[i] == 0:
            for j in range(i+1,n):
                if s[j] == 0:
                    if f[i] == f[j]:
                        s[i] = -1
                        s[j] = -1
                        for k in v[i]:
                            s[k] -= 1
                        for k in v[j]:
                            s[k] -= 1
                        dfs(s,d+2,f,v)
                        s[i] = 0
                        s[j] = 0
                        for k in v[i]:
                            s[k] += 1
                        for k in v[j]:
                            s[k] += 1

def solve(n):
    p = [[int(x) for x in sys.stdin.readline().split()] for i in range(n)]
    v = [[] for i in range(n)]
    f = [0]*n
    s = [0]*n
    for i in range(n):
        x,y,r,f[i] = p[i]
        for j in range(i+1,n):
            xj,yj,rj,c = p[j]
            if (x-xj)**2+(y-yj)**2 < (r+rj)**2:
                v[i].append(j)
                s[j] += 1
    dfs(s,0,f,v)
    print(ans)
while 1:
    n = int(sys.stdin.readline())
    ans = 0
    if n == 0:
        break
    solve(n)
"""

#2003_D
"""
import sys
def root(x,par):
    if par[x] == x:
        return x
    par[x] = root(par[x],par)
    return par[x]

def unite(x,y,par,rank):
    x = root(x,par)
    y = root(y,par)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

def solve(n):
    p = [[float(x) for x in sys.stdin.readline().split()] for i in range(n)]
    v = []
    for i in range(n):
        for j in range(i):
            xi,yi,zi,ri = p[i]
            xj,yj,zj,rj = p[j]
            d = max(0,((xi-xj)**2+(yi-yj)**2+(zi-zj)**2)**0.5-(ri+rj))
            v.append((i,j,d))
    par = [i for i in range(n)]
    rank = [0]*n
    v.sort(key = lambda x:x[2])
    ans = 0
    for x,y,d in v:
        if root(x,par) != root(y,par):
            unite(x,y,par,rank)
            ans += d
    print("{:.3f}".format(round(ans,3)))

while 1:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    solve(n)
"""

#2009_D
"""
import sys
from heapq import heappop,heappush
from collections import defaultdict
def solve(n,m):
    s,g = [int(x) for x in sys.stdin.readline().split()]
    s -= 1
    g -= 1
    e = [[] for i in range(n)]
    for i in range(m):
        a,b,d,c = [int(x) for x in sys.stdin.readline().split()]
        a -= 1
        b -= 1
        e[a].append((b,d,c))
        e[b].append((a,d,c))
    dist = defaultdict(lambda : float("inf"))
    dist[(s,0,-1)] = 0
    q = [(0,s,0,-1)]
    while q:
        dx,x,v,p = heappop(q)
        if x == g and v == 1:
            print(dx)
            return
        for i in range(-1,2):
            v_ = v+i
            if v_ < 1 :continue
            for y,d,c in e[x]:
                if p == y:
                    continue
                if v_ > c:
                    continue
                z = d/v_
                if dx+z < dist[(y,v_,x)]:
                    dist[(y,v_,x)] = dx+z
                    heappush(q,(dist[(y,v_,x)],y,v_,x))
    print("unreachable")
    return

while 1:
    n,m = [int(x) for x in sys.stdin.readline().split()]
    if n == 0:
        break
    solve(n,m)
"""

#2016_D
"""
import sys
def solve(n):
    w = [int(x) for x in sys.stdin.readline().split()]
    dp = [[0]*(n+1) for i in range(n+1)]
    for le in range(n+1):
        for l in range(n):
            r = l+le
            if r > n:break
            if not (r-l)%2 and abs(w[l]-w[r-1]) < 2:
                if dp[l+1][r-1] == r-l-2:
                    dp[l][r] = r-l
                    continue
            for k in range(l+1,r):
                if dp[l][k] + dp[k][r] > dp[l][r]:
                    dp[l][r] = dp[l][k] + dp[k][r]
    print(dp[0][n])
while 1:
    n = int(sys.stdin.readline())
    if not n:
        break
    solve(n)
"""
#2009_D
"""
alp = list("abcdefghijklmnopqrstuvwxyz")
c = {}
key = {}
for i in range(25):
    c[alp[i]] = alp[i+1]
    key[alp[i]] = i
key["z"] = 25

def dfs(i,k,f,n):
    global ans
    if i == n:
        for j in k:
            if f[key[j]]:
                break
        else:
            ans.append(k)
    else:
        dfs(i+1,k+s[i],f,n)
        if s[i] != "z" and f[key[s[i]]+1]:
            f[key[s[i]]+1] = 0
            dfs(i+1,k+c[s[i]],f,n)
            f[key[s[i]]+1] = 1

def solve(s):
    global ans
    n = len(s)
    d = {}
    for i in s:
        d[i] = 1
    f = [1]*26
    f[0] = 0
    dfs(0,"",f,n)
    ans.sort()
    print(len(ans))
    if len(ans) < 10:
        for i in ans:
            print(i)
    else:
        for i in ans[:5]:
            print(i)
        for i in ans[-5:]:
            print(i)
while 1:
    s = input()
    ans = []
    if s == "#":
        break
    solve(s)
"""

#2004_D
"""
import sys
from collections import defaultdict
while 1:
    d = defaultdict(list)
    d_ = defaultdict(list)
    n = int(sys.stdin.readline())
    if n == 0:break
    point = [[float(x) for x in sys.stdin.readline().split()] for i in range(n)]
    ans = 1
    for i in range(n):
        p,q = point[i]
        for j in range(n):
            if i == j:continue
            s,t = point[j]
            if (p-s)**2+(q-t)**2 > 4:
                continue
            d[i].append(j)
            if j > i:
                d_[i].append(j)

    for i in range(n):
        p,q = point[i]
        for j in d_[i]:
            s,t = point[j]
            v = (t-q,p-s)
            m = ((p+s)/2,(q+t)/2)
            l = 0
            r = 10000
            while r-l > 0.0001:
                k = (l+r)/2
                a,b = m[0]+k*v[0],m[1]+k*v[1]
                if (p-a)**2+(q-b)**2 < 1:
                    l = k
                else:
                    r = k
            ans_ = 2
            for l in d[i]:
                if l == j:
                    continue
                x,y = point[l]
                if (x-a)**2+(y-b)**2 < 1:
                    ans_ += 1

            if ans_ > ans:
                ans = ans_
                if ans == n:break

            k = -k
            a,b = m[0]+k*v[0],m[1]+k*v[1]
            ans_ = 2
            for l in d[i]:
                if l == j:
                    continue
                x,y = point[l]
                if (x-a)**2+(y-b)**2 < 1:
                    ans_ += 1

            if ans_ > ans:
                ans = ans_
                if ans == n:break
        if ans == n:break
    print(ans)
"""
#2010_D
import sys
from collections import defaultdict,deque
d = [(1,0),(-1,0),(0,1),(0,-1)]
def bfs(b,a,k):
    q = deque([(b,a)])
    bfs_map[b][a] = k
    g = a+0.5
    p = s[b][a]
    su = 1
    while q:
        y,x = q.popleft()
        for dy,dx in d:
            y_ = y+dy
            x_ = x+dx
            if 0 <= y_ < h and 0 <= x_ < w:
                if bfs_map[y_][x_] < 0 and s[y_][x_] == p:
                    bfs_map[y_][x_] = k
                    q.append((y_,x_))
                    g += x_+0.5
                    su += 1
    f[k] = (g,su)

def dfs(x):
    if g[x] != None:
        return g[x]
    g[x] = [f[x][0],f[x][1]]
    for y in v[x]:
        g_ = dfs(y)
        g[x][0] += g_[0]
        g[x][1] += g_[1]
    return g[x]

while 1:
    w,h = [int(x) for x in sys.stdin.readline().split()]
    if w == 0:
        break
    s = [sys.stdin.readline()[:-1] for i in range(h)]
    f = defaultdict(lambda : 0)
    bfs_map = [[-1]*w for i in range(h)]
    k = 0
    for y in range(h)[::-1]:
        for x in range(w):
            if s[y][x] != "." and bfs_map[y][x] < 0:
                bfs(y,x,k)
                k += 1

    v = [[] for i in range(k)]
    l = [float("inf")]*k
    r = [0]*k
    fl = [1]*k

    for y in range(h):
        for x in range(w):
            if bfs_map[y][x] > -1:
                b = bfs_map[y][x]
                if y == h-1 or (bfs_map[y+1][x] != b and bfs_map[y+1][x] > -1):
                    l[b] = min(l[b],x)
                    r[b] = max(r[b],x+1)
                    if y < h-1 and fl[b]:
                        v[bfs_map[y+1][x]].append(b)
                        fl[b] = 0
    g = [None]*k
    for i in range(k):
        dfs(i)
        gx = g[i][0]/g[i][1]
        if gx <= l[i] or r[i] <= gx:
            print("UNSTABLE")
            break
    else:
        print("STABLE")

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

eps = 1e-4
def bsa(f, mi, ma):
    mm = -1
    while ma > mi + eps:
        mm = (ma+mi) / 2.0
        if f(mm):
            mi = mm + eps
        else:
            ma = mm
    if f(mm):
        return mm + eps
    return mm

def main():
    rr = []

    def f(w,h):
        a = [['.'] * (w+2)] + [['.'] + [c for c in S()] + ['.'] for _ in range(h)] + [['.'] * (w+2)]
        sf = [[None]*(w+2) for _ in range(h+1)] + [[0] * (w+2)]
        bs = []
        bi = 0
        for i in range(1,h+1):
            for j in range(1,w+1):
                if sf[i][j] or a[i][j] == '.':
                    continue
                bi += 1
                c = a[i][j]
                q = []
                q.append((i,j))
                sf[i][j] = bi
                qt = 0
                while len(q) > qt:
                    qi,qj = q[qt]
                    qt += 1
                    for di,dj in dd:
                        ni = qi + di
                        nj = qj + dj
                        if sf[ni][nj] or a[ni][nj] != c:
                            continue
                        sf[ni][nj] = bi
                        q.append((ni,nj))
                bs.append(q)

        # print('\n'.join(' '.join(map(lambda x: '.' if x is None else str(x), _)) for _ in sf))
        def _f(i):
            l = inf
            r = -inf
            bt = set()
            tt = set()
            bi = bs[i-1]
            wd = collections.defaultdict(int)
            for si,sj in bi:
                wd[sj] += 1
                c = sf[si+1][sj]
                if not c is None and c != i:
                    bt.add(c)
                    if l > sj:
                        l = sj
                    if r < sj:
                        r = sj
                c = sf[si-1][sj]
                if not c is None and c != i:
                    tt.add(c)
            if len(bt) != 1:
                return
            for ti in tt:
                td = _f(ti)
                if td is None:
                    return
                for k in td.keys():
                    wd[k] += td[k]
            def __f(j):
                w = 0
                for k in wd.keys():
                    w += (k-j) * wd[k]
                # print('jw',j,w)
                return w > 0

            w = bsa(__f, 0, 11) + 0.5
            # print('lr',l,r)
            # print(i,wd)
            # print(i,w)
            if w < l + eps*10 or w > r + 1 - eps*10:
                return
            return wd

        bti = -1
        for j in range(1,w+1):
            if sf[-2][j]:
                bti = sf[-2][j]
        # print('bti', bti)
        r = _f(bti)
        if r is None:
            return 'UNSTABLE'
        return 'STABLE'

    while 1:
        n,m = LI()
        if n == 0 and m == 0:
            break
        rr.append(f(n,m))
        # print('rr', rr[-1])

    return '\n'.join(map(str,rr))


print(main())

Submission status: Accepted

Solution code:
while True:
  w, h = map(int, input().split())
  if w == 0:
    break

  mp = [[0] + list(input()) + [0] for _ in range(h)]
  mp.insert(0, [0] * (w + 2))
  mp.append([0] * (w + 2))
  for y in range(1, h + 1):
    for x in range(1, w + 1):
      if mp[y][x] == ".":
        mp[y][x] = 0
      else:
        mp[y][x] = int(mp[y][x])

  last_id = 10
  vec = ((0, 1), (0, -1), (1, 0), (-1, 0))
  
  def update(last_id, target, x, y):
    if mp[y][x] != target:
      return
    mp[y][x] = last_id
    for dx, dy in vec:
      update(last_id, target, x + dx, y + dy)
  
  for y in range(1, h + 1):
    for x in range(1, w + 1):
      if 1 <= mp[y][x] <= 9:
        update(last_id, mp[y][x], x, y)
        last_id += 1

  node_num = last_id - 10

  edges = [set() for _ in range(node_num)]
  for y in range(1, h + 1):
    for x in range(1, w + 1):
      if mp[y - 1][x] != mp[y][x] and mp[y - 1][x] != 0 and mp[y][x] != 0:
        edges[mp[y][x] - 10].add(mp[y - 1][x] - 10)

  for x in range(1, w + 1):
    if mp[h][x] != 0:
      root = mp[h][x] - 10
      break
  
  center = [0] * node_num
  ground = [None] * node_num
    
  for y in range(1, h + 1):
    for x in range(1, w + 1):
      if mp[y][x] != 0:
        target = mp[y][x] - 10
        center[target] += (x + 0.5) / 4
        if mp[y + 1][x] in (0, target + 10):
          continue
        if ground[target] == None:
          ground[target] = [x, x + 1]
        else:
          ground[target][0] = min(ground[target][0], x)
          ground[target][1] = max(ground[target][1], x + 1)

  for x in range(1, w + 1):
    if mp[h][x] == root + 10:
      if ground[root] == None:
        ground[root] = [x, x + 1]
      else:
        ground[root][0] = min(ground[root][0], x)
        ground[root][1] = max(ground[root][1], x + 1)

  total_center = [None] *  node_num
  def get_total_center(node):
    mom = center[node]
    wei = 1
    for to in edges[node]:
      to_wei, to_pos = get_total_center(to)
      mom += to_wei * to_pos
      wei += to_wei

    total_center[node] = mom / wei
    return wei, total_center[node]
  
  get_total_center(root)

  for gr, cen in zip(ground, total_center):
    l, r = gr
    if not (l < cen < r):
      print("UNSTABLE")
      break
  else:
    print("STABLE")