#!/usr/bin/env python3

# Příklad vstupu. Program by ho měl načíst ze vstupu, ale pro
# jednoduchost tomu tak zde není.
N=5 # počet map
R=2; S=2 # rozměry mapy
W=1 # cena režie

mapy = [
	["01","00"],
	["11","10"],
	["00","10"],
	["11","00"],
	["10","11"]]

class hrana:
	#konce je dvojice (u,v), vrcholy na konci hrany
	def __init__(self,konce,vaha):
		self.konce = konce
		self.vaha = vaha

# spočítá vzdálenost mezi mapami
# jedna mapa je dvourozměrné pole (např. pole stringů)
def vzdalenost(a,b):
	v = 0
	for i in range(R):
		for j in range(S):
			v+= (a[i][j]!=b[i][j])
	return v

# Vytvoříme si graf, vrcholy jsou mapy, hrany jsou mezi všemi mapami, hrana
# má váhu danou (počtem rozdílných políček)*W.
# Do grafu přidáme ještě jeden speciální vrchol (má číslo N, vrcholy
# indexujeme od 0), od něj vedou hrany do každé mapy délky R*S.

hrany = [] # bude to seznam hran grafu
for i in range(N):
	for j in range(i+1,N):
		hrany.append(hrana((i,j),W*vzdalenost(mapy[i],mapy[j])))
	hrany.append(hrana((i,N),R*S))

# Nalezneme minimální kostru grafu. Vede-li v ní hrana mezi mapami (A,B),
# znamená to, že nejdřív stáhneme mapu A a od ní diferencí mapu B nebo
# opačně.
# Hrana ze speciálního vrcholu do mapy znamená, že ji stáhneme přímo ze
# serveru.

# hrany setřídíme přihrádkově podle váhy
def radixsort(hrany):
	p = [[] for _ in range(R*S+1)]
	for i in hrany:
		p[i.vaha // W].append(i)
	hrany = []
	for i in p:
		for j in i:
			hrany.append(j)
	return hrany

hrany = radixsort(hrany)

# DFU (převzato beze změny z kuchařky o minimální kostře)
class DFU:
	def __init__(self, n):
		self.parent = [0] * n
		self.rank = [0] * n

	def root(self, v):
		if self.parent[v] == 0:
			return v
		else:
			self.parent[v] = self.root(self.parent[v])
			return self.parent[v]

	def find(self, v, w):
		return (self.root(v) == self.root(w))

	def union(self, v, w):
		v = self.root(v)
		w = self.root(w)
		if v == w:
			return

		if self.rank[v] == self.rank[w]:
			self.parent[v] = w
			self.rank[w] = self.rank[w]+1

		elif self.rank[v] < self.rank[w]:
			self.parent[v] = w

		else:
			self.parent[w] = v

# najdem minimální kostru grafu
dfu = DFU(N+1)
kostra = [] # bude uložená jako seznam hran
for h in hrany:
	if not dfu.find(h.konce[0], h.konce[1]):
		kostra.append(h)
		dfu.union(h.konce[0], h.konce[1])

# ze seznamu hran kostry uděláme seznam sousedů...
graf = [[] for _ in range(N+1)]
for k in kostra:
	graf[k.konce[0]].append(k.konce[1])
	graf[k.konce[1]].append(k.konce[0])

# ...abychom ho mohli projít do šířky a vypsat, v jakém pořadí budeme mapy
# stahovat
print("Ze serveru stáhneme mapy v tomto pořadí:")

hotove = [False] *(N+1)
hotove[N] = True
fronta=[]
for x in graf[N]: # začíná se u serveru
	print("mapu",x,"přímo ze serveru")
	fronta.append(x)
	hotove[x]=True

while fronta:
	x = fronta.pop()
	for y in graf[x]:
		if not hotove[y]:
			fronta.append(y)
			hotove[y]=True
			print("mapu",y,"jako diferenci od mapy",x)