# based god Donald Knuth
# http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
# sám bych to asi nevymyslel


class Cell:
	def __init__(self,col):
		self.left=self
		self.right=self
		self.up=self
		self.down=self
		self.col=col

	def attachRight(self,c):
		"""...-(b)-(self)->  <-(c)-(d)-..."""
		self.right.left=c.left
		c.left.right=self.right
		self.right=c
		c.left=self

	def attachDown(self,c):
		self.down.up=c.up
		c.up.down=self.down
		self.down=c
		c.up=self


class Column(Cell):
	def __init__(self,name):
		super().__init__(self)
		self.name=name
		self.size=0

	def cover(self):
		self.right.left=self.left
		self.left.right=self.right
		r=self.down
		while r is not self:
			c=r.right
			while c is not r:
				c.down.up=c.up
				c.up.down=c.down
				c.col.size-=1
				c=c.right
			r=r.down

	def uncover(self):
		r=self.up
		while r is not self:
			c=r.left
			while c is not r:
				c.col.size+=1
				c.down.up=c
				c.up.down=c
				c=c.left
			r=r.up
		self.right.left=self
		self.left.right=self


class Header(Column):
	def __init__(self):
		super().__init__("head")
		self.up=self.down=self.size=None
		self._res=[]

	def search(self,k=0):
		if self.right is self:
			self.print()
			return True
		if len(self._res)<=k:
			self._res.append(None)

		col=self.chooseCol()
		col.cover()
		row=col.down
		while row is not col:
			self._res[k]=row
			c=row.right
			while c is not row:
				c.col.cover()
				c=c.right
			self.search(k+1)
			c=row.left
			while c is not row:
				c.col.uncover()
				c=c.left
			row=row.down
		col.uncover()

	def chooseCol(self):
		c=self.right
		best=c.size
		res=c
		while c is not self:
			if c.size<best:
				best=c.size
				res=c
			c=c.right
		return res

	def print(self):
		for r in self._res:
			print(r.col.name,end=" ")
			c=r.right
			while c is not r:
				print(c.col.name,end=" ")
				c=c.right
			print()
		print()