import random

class WumpusGame(object):


	def __init__(self, edges=[]):

		
		if edges:
			cave = {}
			N = max([edges[i][0] for i in range(len(edges))])
			for i in range(N):
				exits = [edge[1] for edge in edges if edge[0] == i]
				cave[i] = exits

		
		else:
			cave = {1: [2,3,4], 2: [1,5,6], 3: [1,7,8], 4: [1,9,10], 5:[2,9,11],
				6: [2,7,12], 7: [3,6,13], 8: [3,10,14], 9: [4,5,15], 10: [4,8,16], 
				11: [5,12,17], 12: [6,11,18], 13: [7,14,18], 14: [8,13,19], 
				15: [9,16,17], 16: [10,15,19], 17: [11,20,15], 18: [12,13,20], 
				19: [14,16,20], 20: [17,18,19]}

		self.cave = cave

		self.threats = {}

		self.arrows = 5

		self.arrow_travel_distance = 5		
											
		self.player_pos = -1


	


	def get_safe_rooms(self):
		
		return list(set(self.cave.keys()).difference(self.threats.keys()))


	def populate_cave(self):
		
		for threat in ['bat', 'bat', 'pit', 'pit', 'wumpus']:
			pos = random.choice(self.get_safe_rooms())
			self.threats[pos] = threat
		self.player_pos = random.choice(self.get_safe_rooms())


	def breadth_first_search(self, source, target, max_depth=5):
		
		
		graph = self.cave
		depth = 0

		def search(stack, visited, target, depth):
			if stack == []:					
				return False, -1
			if target in stack:
				return True, depth
			visited = visited + stack
			stack = list(set([graph[v][i] for v in stack for i in range(len(graph[v]))]).difference(visited))
			depth += 1
			if depth > max_depth:			
				return False, depth
			else:							
				return search(stack, visited, target, depth)

		return search([source], [], target, depth)


	


	def print_warning(self, threat):
		
		if threat == 'bat':
			print()
		elif threat == 'pit':
			print()
		elif threat == 'wumpus':
			print()


	def get_players_input(self):
		
		while 1:								

			inpt = input()
			try:								
				mode = str(inpt).lower()
				assert mode in ['s', 'm', 'q']
				break
			except (ValueError, AssertionError):
				print()

		if mode == 'q':							
			return 'q', 0

		while 1:								

			inpt = input()
			try:								
				target = int(inpt)
			except ValueError:
				print()
				continue						

			if mode == 'm':
				try:							
					assert target in self.cave[self.player_pos]
					break
				except AssertionError:
					print()

			elif mode == 's':
				try:							
					bfs = self.breadth_first_search(self.player_pos, target)
					assert bfs[0] == True
					break
				except AssertionError:
					if bfs[1] == -1: 			
						print()
						target = random.choice(self.cave.keys())
					if bfs[1] > self.arrow_travel_distance:				
						print()

		return mode, target


	


	def enter_room(self, room_number):
			
		print(.format(room_number))
		
		if self.threats.get(room_number) == 'bat':
			
			print()
			new_pos = random.choice(self.get_safe_rooms())
			return self.enter_room(new_pos)
		elif self.threats.get(room_number) == 'wumpus':
			print()
			return -1
		elif self.threats.get(room_number) == 'pit':
			print()
			return -1

		
		for i in self.cave[room_number]:
			self.print_warning(self.threats.get(i))

		
		return room_number


	def shoot_room(self, room_number):
		
		print(.format(room_number))
		
		self.arrows -= 1
		threat = self.threats.get(room_number)
		if threat in ['bat', 'wumpus']:
			del self.threats[room_number]		
			if threat == 'wumpus':
				print()
				return -1
			elif threat == 'bat':
				print()
		elif threat in ['pit', None]:
			print()

		
		if self.arrows < 1:		
			print()
			return -1

		
		if random.random() < 0.75:
			
			for room_number, threat in self.threats.items():
				if threat == 'wumpus':
					wumpus_pos = room_number					
			new_pos = random.choice(list(set(self.cave[wumpus_pos]).difference(self.threats.keys())))
			del self.threats[room_number]
			self.threats[new_pos] = 'wumpus'			
			if new_pos == self.player_pos: 
				print()
				return -1

		return self.player_pos


	def gameloop(self):

		print()
		print()
		print()
		self.populate_cave()
		self.enter_room(self.player_pos)

		while 1:

			
			
			

			print(.format(self.player_pos), end=)
			print(.format(*self.cave[self.player_pos]))


			inpt = self.get_players_input()		
			print()								
			if inpt[0] == 'm':					
				target = inpt[1] 
				self.player_pos = self.enter_room(target)
			elif inpt[0] == 's':				
				target = inpt[1]
				self.player_pos = self.shoot_room(target)
			elif inpt[0] == 'q':				
				self.player_pos = -1

			if self.player_pos == -1:			
				break							
												

		print()
		print()	


if __name__ == '__main__':						
	
	
	
	

	

	WG = WumpusGame()
	WG.gameloop()