#!/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"]]

# a, b jsou čísla map
def vaha(a,b):
	if a==N or b==N: # "mapa" s číslem N je server
		return R*S
	v = 0
	for i in range(R):
		for j in range(S):
			v+= (mapy[a][i][j]!=mapy[b][i][j])
	return v*W

class Q:
	# n je počet vrcholů, limit je horní mez klíče
	# vrcholy mají indexy 0..n-1
	def __init__(self, n, limit):
		self.p = [ [ False for j in range(n) ] for i in range(limit+1) ] # pole
		self.inQ = [ False for i in range(n) ] # udává, zda je vrchol v Q
		self.keys = [ 0 for i in range(n) ] #
		self.v = 0 # aktuální počet vrcholů
		self.n = n # maximální počet vrcholů

	# vloží vrchol s indexem x a hodnotou key do Q
	def push(self, x, key):
		self.p[key][x] = True
		self.keys[x] = key
		self.inQ[x] = True
		self.v += 1

	# změní hodnotu klíče vrcholu x
	def change_key(self, x, newkey):
		self.p[self.keys[x]][x] = False
		self.keys[x] = newkey
		self.p[newkey][x] = True

	def get_key(self, x):
		return self.keys[x]

	# vyjme z Q vrchol s nejnižším klíčem
	def extract_min(self):
		for i in self.p:
			for j in range(self.n):
				if i[j]:
					self.n -= 1
					self.inQ[j] = False
					return j
		return None

	def is_empty(self):
		return self.n == 0

	# udává, zda vrchol x je v Q
	def contains(self, x):
		return self.inQ[x]

# Jarníkův algoritmus:
q = Q(N+1, R*S+1)
for i in range(N+1):
	q.push(i, R*S+1) # R*S+1 je pro nás nekonečno
q.change_key(N,0) # server bude startovní vrchol

t = [ None for i in range(N+1) ] # zde bude kostra

while not q.is_empty():
	u = q.extract_min()
	for v in range(N+1): # všichni sousedé u
		if v!=u and q.contains(v):
			w = vaha(u,v)
			# hrany těžší než R*S klidně z grafu vyhodíme, v kostře se neobjeví
			# a budeme to mít jednodušší
			if w <= R*S:
				k = q.get_key(v)
				k *= W if k<R*S else 1
				if k > w:
					# do Q ukládáme váhu hrany děleno W, aby se tím dobře indexovalo
					# ale je-li váha R*S, pak ji nedělíme
					q.change_key(v, w // (W if w!=R*S else 1)) # předpokládáme W kladné
					t[v] = u

# teď jen vypíšeme pořadí stahování
d = [ [] for i in range(N+1) ] # bude to seznam sousedů
fronta = [] # budem procházet strom do šířky od serveru
hotovo = [ False for i in range(N+1) ]
print("Ze serveru stáhneme mapy v tomto pořadí:")
for i in range(N):
	if t[i]==N:
		print("mapu",i,"přímo ze serveru")
		hotovo[i] = True
		fronta.append(i)
	d[t[i]].append(i)

while fronta:
	x = fronta.pop()
	for i in d[x]:
		print("mapu",i,"jako diferenci od mapy",x)
		fronta.append(i)