import sys

# Constants
EMPTY = 0
BLACK = 1
WHITE = 2
BOARD_SIZE = 9
KOMI = 6.5

class GoGame:
    def __init__(self):
        self.board = [[EMPTY for _ in range(BOARD_SIZE)] for _ in range(BOARD_SIZE)]
        self.current_player = BLACK
        self.passes = 0
        self.captured_black = 0
        self.captured_white = 0

    def print_board(self):
        # Column headers: A-H, J (skipping I)
        cols = "ABCDEFGHJ"
        print("   " + " ".join(cols))
        for r in range(BOARD_SIZE):
            row_str = f"{r+1:2} " # Row number
            for c in range(BOARD_SIZE):
                stone = self.board[r][c]
                if stone == EMPTY:
                    row_str += ". "
                elif stone == BLACK:
                    row_str += "X "
                elif stone == WHITE:
                    row_str += "O "
            print(row_str.strip())

    def parse_move(self, move_str):
        move_str = move_str.strip().upper()
        if move_str == "PASS":
            return "PASS"
        
        if len(move_str) != 2:
            return None
        
        col_char = move_str[0]
        row_char = move_str[1]
        
        if col_char not in "ABCDEFGHJ":
            return None
        if not row_char.isdigit():
            return None
            
        col = "ABCDEFGHJ".index(col_char)
        row = int(row_char) - 1
        
        if 0 <= row < BOARD_SIZE:
            return (row, col)
        return None

    def get_group_and_liberties(self, r, c, board_state):
        color = board_state[r][c]
        if color == EMPTY:
            return set(), set()
            
        group = set()
        liberties = set()
        stack = [(r, c)]
        group.add((r, c))
        
        while stack:
            curr_r, curr_c = stack.pop()
            neighbors = [
                (curr_r-1, curr_c), (curr_r+1, curr_c),
                (curr_r, curr_c-1), (curr_r, curr_c+1)
            ]
            
            for nr, nc in neighbors:
                if 0 <= nr < BOARD_SIZE and 0 <= nc < BOARD_SIZE:
                    if board_state[nr][nc] == EMPTY:
                        liberties.add((nr, nc))
                    elif board_state[nr][nc] == color and (nr, nc) not in group:
                        group.add((nr, nc))
                        stack.append((nr, nc))
        return group, liberties

    def place_stone(self, r, c):
        if self.board[r][c] != EMPTY:
            return False, "Occupied"

        # Tentative placement
        self.board[r][c] = self.current_player
        opponent = WHITE if self.current_player == BLACK else BLACK
        
        captured_stones = []
        
        # Check neighbors for captures
        neighbors = [
            (r-1, c), (r+1, c), (r, c-1), (r, c+1)
        ]
        
        for nr, nc in neighbors:
            if 0 <= nr < BOARD_SIZE and 0 <= nc < BOARD_SIZE:
                if self.board[nr][nc] == opponent:
                    group, liberties = self.get_group_and_liberties(nr, nc, self.board)
                    if len(liberties) == 0:
                        captured_stones.extend(list(group))
        
        # Remove captured stones
        for cr, cc in captured_stones:
            self.board[cr][cc] = EMPTY
            if self.current_player == BLACK:
                self.captured_white += 1
            else:
                self.captured_black += 1
        
        # Check suicide
        my_group, my_liberties = self.get_group_and_liberties(r, c, self.board)
        if len(my_liberties) == 0:
            # Revert
            self.board[r][c] = EMPTY
            for cr, cc in captured_stones:
                self.board[cr][cc] = opponent
                if self.current_player == BLACK:
                    self.captured_white -= 1
                else:
                    self.captured_black -= 1
            return False, "Suicide move forbidden"
            
        return True, "Success"

    def calculate_score(self):
        # Area scoring: Stones on board + Territory
        black_score = 0
        white_score = 0
        
        # Count stones
        for r in range(BOARD_SIZE):
            for c in range(BOARD_SIZE):
                if self.board[r][c] == BLACK:
                    black_score += 1
                elif self.board[r][c] == WHITE:
                    white_score += 1
        
        # Count territory
        visited = [[False for _ in range(BOARD_SIZE)] for _ in range(BOARD_SIZE)]
        
        for r in range(BOARD_SIZE):
            for c in range(BOARD_SIZE):
                if self.board[r][c] == EMPTY and not visited[r][c]:
                    # Flood fill empty region
                    region = []
                    stack = [(r, c)]
                    visited[r][c] = True
                    touches_black = False
                    touches_white = False
                    
                    while stack:
                        curr_r, curr_c = stack.pop()
                        region.append((curr_r, curr_c))
                        
                        neighbors = [
                            (curr_r-1, curr_c), (curr_r+1, curr_c),
                            (curr_r, curr_c-1), (curr_r, curr_c+1)
                        ]
                        
                        for nr, nc in neighbors:
                            if 0 <= nr < BOARD_SIZE and 0 <= nc < BOARD_SIZE:
                                if self.board[nr][nc] == BLACK:
                                    touches_black = True
                                elif self.board[nr][nc] == WHITE:
                                    touches_white = True
                                elif self.board[nr][nc] == EMPTY and not visited[nr][nc]:
                                    visited[nr][nc] = True
                                    stack.append((nr, nc))
                    
                    if touches_black and not touches_white:
                        black_score += len(region)
                    elif touches_white and not touches_black:
                        white_score += len(region)
        
        white_score += KOMI
        return black_score, white_score

    def run(self):
        print("Go Game (9x9)")
        print("Black moves first.")
        print("Enter coordinates (e.g., E5) or 'pass'.")
        
        while True:
            self.print_board()
            player_name = "Black" if self.current_player == BLACK else "White"
            prompt = f"{player_name}'s move: "
            
            try:
                user_input = input(prompt)
            except EOFError:
                break
            
            move = self.parse_move(user_input)
            
            if move == "PASS":
                self.passes += 1
                print(f"{player_name} passed.")
                if self.passes >= 2:
                    print("Both players passed. Game Over.")
                    break
                self.current_player = WHITE if self.current_player == BLACK else BLACK
                continue
            elif move is None:
                print("Invalid input. Use format like E5 or 'pass'.")
                continue
            
            r, c = move
            success, msg = self.place_stone(r, c)
            
            if success:
                self.passes = 0
                self.current_player = WHITE if self.current_player == BLACK else BLACK
            else:
                print(f"Invalid move: {msg}")

        b_score, w_score = self.calculate_score()
        print(f"\nFinal Score:")
        print(f"Black: {b_score}")
        print(f"White: {w_score} (includes {KOMI} komi)")
        
        if b_score > w_score:
            print("Black wins!")
        elif w_score > b_score:
            print("White wins!")
        else:
            print("Draw!")

if __name__ == "__main__":
    game = GoGame()
    game.run()