import sys

try: import psyco; psyco.full()
except: pass

class Graph:
    def __init__(self, f):
        self.reset()
        self.read(f)

    def reset(self):
        self.vertex = []
        self.edge = []

    def read(self, f):
        if not isinstance(f, file): f = file(f)
        
        nvertex, nedge = map(int, f.readline().split())
        for i in xrange(nvertex):
            vx, vy, vdeg = map(int, f.readline().split()[:3])
            self.vertex.append((float(vx), float(vy)))
        for i in xrange(nedge):
            v1, v2 = map(int, f.readline().split())
            self.edge.append((v1, v2))

    def split(self, factor = 2):
        oldedge = self.edge
        self.edge = []
        for e in oldedge:
            v1, v2 = self.vertex[e[0]], self.vertex[e[1]]
            prev = e[0]
            for i in xrange(1, factor):
                vertex = ((v1[0] * i + v2[0] * (factor - i)) / factor,
                          (v1[1] * i + v2[1] * (factor - i)) / factor)
                self.edge.append((prev, len(self.vertex)))
                prev = len(self.vertex)
                self.vertex.append(vertex)
            self.edge.append((prev, e[1]))

def load(n):
    return Graph('Graphs\\ch%04d.graph' % n)

def _similarity(src, dest):
    dists = []
    for v in dest.vertex:
        idists = []
        for e in src.edge:
            start, end = src.vertex[e[0]], src.vertex[e[1]]
            if start == end: continue
            delta = (end[0] - start[0], end[1] - start[1])
            vv = (v[0] - start[0], v[1] - start[1])
            factor = (vv[0] * delta[0] + vv[1] * delta[1]) / \
                     (delta[0] ** 2 + delta[1] ** 2)
            if factor < 0: factor = 0
            if factor > 1: factor = 1
            distance = ((vv[0] - factor * delta[0]) ** 2 + \
                        (vv[1] - factor * delta[1]) ** 2) ** 0.5
            idists.append(distance)
        dists.append(min(idists))
    return dists

def similarity(a, b):
    dists = _similarity(a,b) + _similarity(b,a)
    return sum(dists) / len(dists)


g = []
for i in xrange(12):
    gg = load(i+1)
    gg.split()
    g.append(gg)
for i in g:
    for j in g:
        print '%5.1f' % similarity(i, j),
    print