import re


def parse(instruction):
  """
  Take an instruction as a string and return a tuple (output wire, input specification).

  Example input specifications:
  * ("ID", "6") for constant input
  * ("ID", "a") for direct wire input "a"
  * ("NOT", "ab") for negated wire "ab"
  * ("AND", "76", "xy") for bitwise-AND between constant and wire "ab"

  Keyword arguments:
  instruction --- an instruction formatted according to the challenge rules
  """
  match = re.search("^(.*) -> ([a-z]+)$", instruction)
  if match:
    (input_expression, output_wire) = match.groups()

    if " " not in input_expression:
      input_command = ("ID", input_expression)
    elif "NOT" in input_expression:
      submatch = re.search(r"^NOT (\w+)$", input_expression)
      if submatch:
        input_command = ("NOT", submatch.group(1))
      else:
        raise ValueError("Illegal instruction:", instruction)
    else:
      submatch = re.search(r"^(\w+) ([A-Z]+) (\w+)$", input_expression)
      if submatch:
        input_command = (submatch.group(2), submatch.group(1), submatch.group(3))
      else:
        raise ValueError("Illegal instruction:", instruction)

    return (output_wire, input_command)
  else:
    raise ValueError("Illegal instruction:", instruction)