# Claude AI Hamiltonian path finder
class HamiltonianPathSolver:
    def __init__(self, graph):
        self.graph = [list(graph[k]) for k in sorted(graph.keys())]  # adjacency list representation
        self.n = len(graph)
        self.forced_start = None
        self.forced_end = None
        
    def find_hamiltonian_path(self):
        """Main function to find Hamiltonian path with preprocessing"""
        
        # Step 1: Simple but effective preprocessing
        if not self.preprocess():
            return None  # Preprocessing determined no path exists
            
        # Step 2: Determine start points based on preprocessing
        start_candidates = self.get_start_candidates()
        
        # Step 3: Backtrack from each candidate
        for start in start_candidates:
            path = self.backtrack_with_heuristics(start)
            if path:
                return path
                
        return None
    
    def preprocess(self):
        """Perform degree-based preprocessing"""
        degrees = [len(neighbors) for neighbors in self.graph]
        
        # Find leaves (degree 1 vertices)
        leaves = [v for v in range(self.n) if degrees[v] == 1]
        
        print(f"Graph degrees: {degrees}")
        print(f"Leaves found: {leaves}")
        
        # Basic degree analysis
        if len(leaves) > 2:
            print("Too many leaves - impossible")
            return False  # Impossible - too many endpoints needed
            
        if len(leaves) == 2:
            # Must start and end at these leaves
            self.forced_start, self.forced_end = leaves
            print(f"Forced start: {self.forced_start}, Forced end: {self.forced_end}")
        elif len(leaves) == 1:
            # One endpoint is forced
            self.forced_start = leaves[0]
            print(f"Forced start: {self.forced_start}")
            
        # Check for isolated vertices (degree 0)
        isolated = [v for v in range(self.n) if degrees[v] == 0]
        if len(isolated) > 0:
            print(f"Isolated vertices found: {isolated}")
            return len(isolated) == 0  # Can't have isolated vertices
            
        return True
    
    def get_start_candidates(self):
        """Determine which vertices to try as starting points"""
        if self.forced_start is not None:
            return [self.forced_start]
            
        # Try all vertices, but prefer those with lower degree
        candidates = list(range(self.n))
        candidates.sort(key=lambda v: len(self.graph[v]))
        print(f"Start candidates (by degree): {candidates}")
        
        return candidates
    
    def backtrack_with_heuristics(self, start):
        """Enhanced backtracking with simple heuristics"""
        path = [start]
        visited = 1 << start  # Bitmask for visited vertices
        
        print(f"Starting backtrack from vertex {start}")
        result = self.backtrack_dfs(path, visited, start, 0)
        return result
    
    def backtrack_dfs(self, path, visited, current, depth):
        """DFS with heuristic pruning"""
        
        # Success condition
        if len(path) == self.n:
            # Check if we ended at forced end (if any)
            if self.forced_end is None or current == self.forced_end:
                print(f"Found complete path: {path}")
                return path[:]
            else:
                print(f"Path complete but wrong endpoint. Expected {self.forced_end}, got {current}")
            return None
        
        # Basic connectivity pruning
        if not self.can_reach_remaining(current, visited):
            return None
        
        # Get neighbors and sort them heuristically
        neighbors = [v for v in self.graph[current] if not (visited & (1 << v))]
        
        # Heuristic: prefer vertices with fewer unvisited neighbors (more constrained)
        neighbors.sort(key=lambda v: self.count_unvisited_neighbors(v, visited))
        
        if depth < 3:  # Only print for shallow depths to avoid spam
            print(f"Depth {depth}: At vertex {current}, trying neighbors {neighbors}")
        
        for next_vertex in neighbors:
            # Make move
            path.append(next_vertex)
            new_visited = visited | (1 << next_vertex)
            
            # Recursive call
            result = self.backtrack_dfs(path, new_visited, next_vertex, depth + 1)
            if result:
                return result
                
            # Backtrack
            path.pop()
            
        return None
    
    def can_reach_remaining(self, current, visited):
        """Check if we can reach all unvisited vertices from current position"""
        unvisited = []
        for v in range(self.n):
            if not (visited & (1 << v)):
                unvisited.append(v)
                
        if not unvisited:
            return True
            
        # Simple reachability check using BFS
        reachable = {current}
        queue = [current]
        
        while queue:
            v = queue.pop(0)
            for neighbor in self.graph[v]:
                if neighbor not in reachable and not (visited & (1 << neighbor)):
                    reachable.add(neighbor)
                    queue.append(neighbor)
                    
        # Can we reach all unvisited vertices?
        for v in unvisited:
            if v not in reachable:
                return False
                
        return True
    
    def count_unvisited_neighbors(self, vertex, visited):
        """Count how many unvisited neighbors a vertex has"""
        count = 0
        for neighbor in self.graph[vertex]:
            if not (visited & (1 << neighbor)):
                count += 1
        return count

# Simplified interface function
def solve_hamiltonian_path(adjacency_list, verbose=False):
    """
    Solve Hamiltonian path problem with basic preprocessing
    
    Args:
        adjacency_list: List of lists, where adjacency_list[i] contains neighbors of vertex i
        verbose: Whether to print debug information
    
    Returns:
        List representing Hamiltonian path, or None if no path exists
    """
    if not verbose:
        # Temporarily redirect print to suppress output
        import sys
        from io import StringIO
        old_stdout = sys.stdout
        sys.stdout = StringIO()
        
    try:
        solver = HamiltonianPathSolver(adjacency_list)
        result = solver.find_hamiltonian_path()
        return result
    finally:
        if not verbose:
            sys.stdout = old_stdout

# Test examples
tests = [
"+--------+\n"+
"|........|\n"+
"|...B....|\n"+
"|........|\n"+
"|........|\n"+
"|........|\n"+
"|...B....|\n"+
"|........|\n"+
"|........|\n"+
"+--------+",

"+--------+\n"+
"|........|\n"+
"|...B....|\n"+
"|........|\n"+
"|.....B..|\n"+
"|........|\n"+
"|...B....|\n"+
"|........|\n"+
"|........|\n"+
"+--------+",

"+--------+\n"+
"|........|\n"+
"|...B....|\n"+
"|........|\n"+
"|........|\n"+
"|........|\n"+
"|...B....|\n"+
"|........|\n"+
"|.....B..|\n"+
"+--------+",

"+--------+\n"+
"|........|\n"+
"|...B....|\n"+
"|.B......|\n"+
"|........|\n"+
"|........|\n"+
"|...B....|\n"+
"|........|\n"+
"|.B...B..|\n"+
"+--------+",

"+--------+\n"+
"|........|\n"+
"|...B....|\n"+
"|.B......|\n"+
"|........|\n"+
"|........|\n"+
"|...BB...|\n"+
"|........|\n"+
"|.B...B..|\n"+
"+--------+",

"+--------+\n"+
"|........|\n"+
"|.B......|\n"+
"|.B..B...|\n"+
"|........|\n"+
"|........|\n"+
"|.B..B...|\n"+
"|.B......|\n"+
"|........|\n"+
"+--------+",

"+--------+\n"+
"|...B....|\n"+
"|........|\n"+
"|.B......|\n"+
"|......B.|\n"+
"|......B.|\n"+
"|.B......|\n"+
"|......BB|\n"+
"|BB......|\n"+
"+--------+",

"+--------+\n"+
"|...BB...|\n"+
"|........|\n"+
"|..B..B..|\n"+
"|....B...|\n"+
"|....B...|\n"+
"|..B.....|\n"+
"|.B....B.|\n"+
"|........|\n"+
"+--------+",

"+--------+\n"+
"|........|\n"+
"|.B.B..B.|\n"+
"|........|\n"+
"|.B..B.B.|\n"+
"|........|\n"+
"|.B.B..B.|\n"+
"|........|\n"+
"+--------+",

"+----------+\n"+
"|..........|\n"+
"|..........|\n"+
"|..........|\n"+
"|..B.B....B|\n"+
"|.B...B...B|\n"+
"|.....B....|\n"+
"|..........|\n"+
"|.B......B.|\n"+
"|....B.....|\n"+
"|.B..BB..B.|\n"+
"+----------+",

"+--------+\n"+
"|........|\n"+
"|.BBBBBB.|\n"+
"|.BBBBBB.|\n"+
"|.BBBBBB.|\n"+
"|.BBBBBB.|\n"+
"|.BBBBBB.|\n"+
"|.BBBBBB.|\n"+
"|........|\n"+
"+--------+",

"+---------+\n"+
"|.........|\n"+
"|.B.B.B.B.|\n"+
"|..B.B.B..|\n"+
"|.B.B.B.B.|\n"+
"|..B.B.B..|\n"+
"|.B.B.B.B.|\n"+
"|..B.B.B..|\n"+
"|.B.B.B.B.|\n"+
"|.........|\n"+
"+---------+",

"+---------+\n"+
"|.B......B|\n"+
"|.B.......|\n"+
"|......B..|\n"+
"|.........|\n"+
"|....B....|\n"+
"|.....B...|\n"+
"|.........|\n"+
"|.......B.|\n"+
"|.........|\n"+
"+---------+",

"+---------+\n"+
"|.........|\n"+
"|...BBB...|\n"+
"|..B...B..|\n"+
"|......B..|\n"+
"|.....B...|\n"+
"|....B....|\n"+
"|....B....|\n"+
"|.........|\n"+
"|....B....|\n"+
"|.........|\n"+
"+---------+",

"+----------------+\n"+
"|B.............B.|\n"+
"|.B..........B...|\n"+
"|................|\n"+
"|..B........B....|\n"+
"|....B.....B.....|\n"+
"|.....B..B.......|\n"+
"|.......B........|\n"+
"|......B.........|\n"+
"|......B.B.......|\n"+
"|.....B....B.....|\n"+
"|................|\n"+
"|....B......B....|\n"+
"|..B.........B...|\n"+
"|.B............B.|\n"+
"|................|\n"+
"|B..............B|\n"+
"+----------------+",

"+--------+\n"+
"|........|\n"+
"|...B....|\n"+
"|........|\n"+
"|..B.....|\n"+
"|........|\n"+
"|...B....|\n"+
"|........|\n"+
"|........|\n"+
"+--------+",      # no solution

"+------------------+\n"+
"|.B...B...B........|\n"+
"|B.................|\n"+
"|.....B.B.....B....|\n"+
"|..............B...|\n"+
"|..................|\n"+
"|..............B...|\n"+
"|.B.......B........|\n"+
"|..................|\n"+
"|..................|\n"+
"|..................|\n"+
"|.......B.B........|\n"+
"|..................|\n"+
"|..................|\n"+
"|..................|\n"+
"|..................|\n"+
"|..B........B......|\n"+
"|...............B..|\n"+
"|..................|\n"+
"|..................|\n"+
"|..............B...|\n"+
"|..................|\n"+
"|..........B.......|\n"+
"+------------------+",

"+------------------------+\n"+
"|.....................B..|\n"+
"|........................|\n"+
"|............B...........|\n"+
"|........................|\n"+
"|........................|\n"+
"|......B....B.........B..|\n"+
"|........................|\n"+
"|...................B....|\n"+
"|........................|\n"+
"|........................|\n"+
"|........B..B............|\n"+
"|........................|\n"+
"|........................|\n"+
"|........B...............|\n"+
"|B.......................|\n"+
"|.B......................|\n"+
"|.............BB....B....|\n"+
"|............B.....B.....|\n"+
"|.................B......|\n"+
"|........................|\n"+
"|........................|\n"+
"|........................|\n"+
"|........................|\n"+
"|............B...........|\n"+
"|........................|\n"+
"|........................|\n"+
"|........................|\n"+
"|........................|\n"+
"+------------------------+"

    ]
from collections import defaultdict
    
def switch_bulbs(g):
    grid = [x[1:-1] for x in g.split('\n')[1:-1]]
    hrz, vrt, d1, d2, pos = defaultdict(set), defaultdict(set), defaultdict(set), defaultdict(set), []
    n, m = len(grid), len(grid[0])
    inv = {}
    num = 0
    for i in range(n):
        for j in range(m):
            if grid[i][j] != '.':
                pos.append((i, j))
                inv[(i, j)] = num
                hrz[i].add((i, j))
                vrt[j].add((i, j))
                d1[i + j].add((i, j))
                d2[i - j].add((i, j))
                num += 1
    adj = {i: set() for i in range(num)}

    for i, j in pos:
        idx = inv[(i, j)]
        for u, v in hrz[i]:
            r = range(j + 1, v) if j < v else range(v + 1, j)            
            if (u, v) != (i, j) and all(grid[i][y] == '.' for y in r):
                adj[idx].add(inv[(u, v)])
        for u, v in vrt[j]:
            r = range(i + 1, u) if i < u else range(u + 1, i)
            if (u, v) != (i, j) and all(grid[x][j] == '.' for x in r):
                adj[idx].add(inv[(u, v)])
        for u, v in d1[i + j]:
            r = range(1, v - j) if j < v else range(-1, v - j, -1)
            if (u, v) != (i, j) and all(grid[i - k][j + k] == '.' for k in r if 0 <= i - k < n and 0 <= j + k < m):
                adj[idx].add(inv[(u, v)])
        for u, v in d2[i - j]:
            r = range(1, v - j) if j < v else range(-1, v - j, -1)
            if (u, v) != (i, j) and all(grid[i + k][j + k] == '.' for k in r if 0 <= i + k < n and 0 <= j + k < m):
                adj[idx].add(inv[(u, v)]) 


    solver = HamiltonianPathSolver(adj)
    result = solver.find_hamiltonian_path()
    if result is None:
        return None
    ans = [pos[i] for i in result] 
    return ans
    
for t in tests:
    r = switch_bulbs(t)
    print(r)
# print("=== Test 3: ===")
# # Two separate edges: 0-1 and 2-3
# graph3 = [
#     [1,2],     
#     [0,2,3,4],      
#     [0,1,3,4],      
#     [1,2,4,5],
#     [2,3,5],
#     [3, 4]
# ]

# path3 = solve_hamiltonian_path(graph3)
# print(f"Result: {path3}")