import json
import re
import ast

def extract_last_code_block(text: str) -> str:
    """
    Extract the last code block from the given text.
    
    Args:
        text (str): The input text containing code blocks
        
    Returns:
        str: The content of the last code block, or None if no code block is found
    """
    code_blocks = re.findall(r'```.*?\n(.*?)```', text, re.DOTALL)
    if not code_blocks:
        code_blocks = re.findall(r'```(.*?)```', text, re.DOTALL)
    return code_blocks[-1].strip() if code_blocks else None

def is_valid_hamiltonian_path(num_nodes: int, path: list, edges: set) -> bool:
    """
    Check if the provided path is a valid Hamiltonian path (undirected).
    
    Args:
        num_nodes (int): Number of nodes in the graph
        path (list): The path to check
        edges (set): Set of edges in the graph
        
    Returns:
        bool: True if the path is a valid Hamiltonian path, False otherwise
    """
    if len(path) != num_nodes:
        return False
    
    if len(set(path)) != num_nodes:
        return False
    
    if set(path) != set(range(num_nodes)):
        return False
    
    for i in range(num_nodes - 1):
        u = path[i]
        v = path[i + 1]
        if (min(u, v), max(u, v)) not in edges:
            return False
    return True

def parse_edges_from_question(question: str) -> tuple:
    """
    Parse the edges from the 'question' field in the meta.
    
    Args:
        question (str): The question string containing graph information
        
    Returns:
        tuple: (number of nodes, set of edges)
    """
    edges = set()
    lines = question.strip().split("\n")
    
    num_nodes = int(lines[0].strip())
    
    for line in lines[1:]:
        u, v = map(int, line.split())
        edges.add((min(u, v), max(u, v)))
    
    return num_nodes, edges

def verify(pred: str, answer: str, meta: dict) -> int:
    """
    Verify if the model's prediction matches the gold answer.
    
    Args:
        pred (str): The model's prediction
        answer (str): The correct answer
        meta (dict): Additional metadata containing the graph information
        
    Returns:
        int: 1 if the prediction is correct, 0 otherwise
    """
    if isinstance(answer, str):
        try:
            answer = json.loads(answer)
        except json.JSONDecodeError:
            pass
    
    if isinstance(meta, str):
        meta = json.loads(meta)
    elif not isinstance(meta, dict):
        raise ValueError('meta should be dict or str')

    final_answer = extract_last_code_block(pred)
    if not final_answer:
        return 0
    
    try:
        pattern = r'\[([\d\s,]+)\]'
        matches = re.findall(pattern, final_answer)
        if matches:
            final_answer = [int(x.strip()) for x in matches[0].split(',') if x.strip()]
        else:
            return 0
    except Exception:
        return 0
    
    if isinstance(final_answer, str):
        final_answer = final_answer.strip()
    elif not isinstance(final_answer, list):
        return 0
    
    if isinstance(answer, str) and answer.strip() == "NO":
        return 1 if final_answer == "NO" else 0

    try:
        if isinstance(final_answer, str):
            path = json.loads(final_answer)
        elif isinstance(final_answer, list):
            path = final_answer
        else:
            return 0

        if not all(isinstance(x, int) for x in path):
            return 0
    except (json.JSONDecodeError, ValueError):
        return 0
    
    num_nodes, edges = parse_edges_from_question(meta.get('question', ''))
    
    if is_valid_hamiltonian_path(num_nodes, path, edges):
        return 1
    return 0
