return (function()

local builders = {}

local function register(name, f)

  buildersname = f

end

register('llpeg', function() return require [[Module:User:Cscott/llpeg]] end)



register('util', function(myrequire)

local function read_wiki_input(func)

    return function (frame, ...)

      if type(frame)=='string' then

        frame = { args = { frame, ... } }

      end

      local title = mw.title.new(frame.args1])

      local source = title:getContent()

      if source == nil then

        error("Can't find title " .. tostring(title))

      end

      source = source:gsub("^%s*<syntaxhighlight[^>]*>\n?", "", 1)

      source = source:gsub("</syntaxhighlight[^>]*>%s*$", "", 1)

      return func(source, frame.args2], frame.args3])

    end

end



return {

  read_wiki_input = read_wiki_input,

}



end)



register('pqueue', function(myrequire)

--[[  Priority Queue implemented in lua, based on a binary heap.

Copyright (C) 2017 Lucas de Morais Siqueira <lucas.morais.siqueira@gmail.com>

License: zlib

  This software is provided 'as-is', without any express or implied

  warranty. In no event will the authors be held liable for any damages

  arising from the use of this software.

  Permission is granted to anyone to use this software for any purpose,

  including commercial applications, and to alter it and redistribute it

  freely, subject to the following restrictions:

  1. The origin of this software must not be misrepresented; you must not

     claim that you wrote the original software. If you use this software

     in a product, an acknowledgement in the product documentation would be

     appreciated but is not required.

  2. Altered source versions must be plainly marked as such, and must not be

     misrepresented as being the original software.

  3. This notice may not be removed or altered from any source distribution.

]]--

-- modified by xxopxe@gmail.com



local floor = math.floor





local PriorityQueue = {}

PriorityQueue.__index = PriorityQueue



setmetatable(

  PriorityQueue,

  {

    __call = function ()

      local new = {}

      setmetatable(new, PriorityQueue)

      new:initialize()

      return new

    end

  }

)





function PriorityQueue:initialize()

  --[[  Initialization.

    Example:

        PriorityQueue = require "priority_queue"

        pq = PriorityQueue()

    ]]--

  self.heap_val = {}

  self.heap_pri = {}

  self.current_size = 0

end



function PriorityQueue:empty()

  return self.current_size == 0

end



function PriorityQueue:size()

  return self.current_size

end



function PriorityQueue:swim()

  -- Swim up on the tree and fix the order heap property.

  local heap_val = self.heap_val

  local heap_pri = self.heap_pri

  local floor = floor

  local i = self.current_size



  while floor(i / 2) > 0 do

    local half = floor(i / 2)

    if heap_prii < heap_prihalf then

      heap_vali], heap_valhalf = heap_valhalf], heap_vali

      heap_prii], heap_prihalf = heap_prihalf], heap_prii

    end

    i = half

  end

end



function PriorityQueue:put(v, p)

  --[[ Put an item on the queue.

    Args:

        v: the item to be stored

        p(number): the priority of the item

    ]]--

  --

  self.current_size = self.current_size + 1

  self.heap_valself.current_size = v

  self.heap_priself.current_size = p

  self:swim()

end



function PriorityQueue:sink()

  -- Sink down on the tree and fix the order heap property.

  local size = self.current_size

  local heap_val = self.heap_val

  local heap_pri = self.heap_pri

  local i = 1



  while (i * 2) <= size do

    local mc = self:min_child(i)

    if heap_prii > heap_primc then

      heap_vali], heap_valmc = heap_valmc], heap_vali

      heap_prii], heap_primc = heap_primc], heap_prii

    end

    i = mc

  end

end



function PriorityQueue:min_child(i)

  if (i * 2) + 1 > self.current_size then

    return i * 2

  else

    if self.heap_prii * 2 < self.heap_prii * 2 + 1 then

      return i * 2

    else

      return i * 2 + 1

    end

  end

end



function PriorityQueue:pop()

  -- Remove and return the top priority item

  local heap_val = self.heap_val

  local heap_pri = self.heap_pri

  local retval, retprio = heap_val1], heap_pri1

  heap_val1], heap_pri1 = heap_valself.current_size], heap_priself.current_size

  heap_valself.current_size], heap_priself.current_size = nil, nil

  self.current_size = self.current_size - 1

  self:sink()

  return retval, retprio

end



function PriorityQueue:peek()

  -- return the top priority item

  return self.heap_val1], self.heap_pri1

end



return PriorityQueue



end)



register('day25', function(myrequire)

--[[ DAY 25 ]]--

local l = myrequire('llpeg')

local read_wiki_input = myrequire('util').read_wiki_input

local PriorityQueue = myrequire('pqueue')



--[[ PARSING ]]--

local nl = l.P"\n"

local SKIP = l.S" \t"^0



local patt = l.P{

   "Wiring",

   Wiring = l.Ct( l.V"Component" * (nl * l.V"Component")^0 * nl^0) * -1,

   Component = l.Ct( l.Cg(l.V"Name", "name") * SKIP * l.P":" * SKIP * l.Cg(l.V"ConnectionList", "connections")),

   ConnectionList = l.Ct( l.V"Name" * (l.P" " * SKIP * l.V"Name")^0 ),

   Name = l.C( l.R"az"^1 ),

}



local Node = {}

Node.__index = Node

function Node:new(p)

  return setmetatable(p or {}, self)

end

function Node:addEdge(n)

  for _,e in ipairs(self.edges) do

    if e == n then return end

  end

  table.insert(self.edges, n)

end



local function parse(source)

   local ast, errlabel, pos = patt:match(source)

   if not ast then

      error(string.format("Error at pos %s label '%s'", pos, errlabel))

   end

   -- postprocess

   local graph = {}

   -- first create all nodes

   for _,n in ipairs(ast) do

     graphn.name = Node:new{ name=n.name, edges={} }

     for _,n2 in ipairs(n.connections) do

       graphn2 = Node:new{ name=n2, edges={} }

     end

   end

   -- now create all edges

   for _,n in ipairs(ast) do

     for _,n2 in ipairs(n.connections) do

       graphn.name]:addEdge(graphn2])

       graphn2]:addEdge(graphn.name])

     end

   end

   return graph

end



local function sortedKeys(tbl)

   local sorted = {}

   for k,_ in pairs(tbl) do

      table.insert(sorted, k)

   end

   table.sort(sorted)

   return sorted

end



local function shortestPath(from, to, checkEdge)

  local seen = {}

  local Q = PriorityQueue()

  Q:put({node=from,prev=nil,len=0}, 0)

  while not Q:empty() do

    local item = Q:pop()

    if item.node == to then return item end

    if seenitem.node == nil then

      seenitem.node = true

      for _,next in ipairs(item.node.edges) do

        if seennext == nil then

          if checkEdge == nil or checkEdge(item.node, next) then

            Q:put({node=next,prev=item,len=item.len+1},item.len+1)

          end

        end

      end

    end

  end

  return nil -- no path found

end



local function part1(source)

  --mw.log(source)

  local graph = parse(source)

  local nodes = sortedKeys(graph)

  -- pick a node arbitrarily

  local n = graphnodes1]]

  local clique1, clique2 = { n }, {}

  -- try to make paths to every other node in the graph.  either:

  -- 1) there are more than 3 possible paths => this node is in the same

  --    component as n

  -- 2) there are only 3 possible paths => this node is in the "other"

  --    component

  for i=2,#nodes do

    local n2 = graphnodesi]]

    local removedEdges = {}

    local function makeKey(a, b) return a.name .. '-' .. b.name end

    local noPathFound = false

    for i=1,4 do

      local path = shortestPath(n, n2, function(a, b)

                                  return removedEdgesmakeKey(a,b)] == nil

      end)

      if path == nil then

        noPathFound = true

        break

      end

      -- add this path to the list of removed edges

      while path.prev ~= nil do

        removedEdgesmakeKey(path.node, path.prev.node)] = true

        removedEdgesmakeKey(path.prev.node, path.node)] = true

        path = path.prev

      end

    end

    if noPathFound then

      table.insert(clique2, n2)

    else

      table.insert(clique1, n2)

    end

  end

  --print(#clique1, #clique2)

  return #clique1 * #clique2

end



--[[ CLI ] ]--

local do_part1 = false

local use_example = false



local filename

if use_example then

  filename = "day25.example"

else

  filename = "day25.input"

end

local source = io.input(filename):read("*a")

print(part1(source))

--[ [ END CLI ]]--



return {

  part1 = read_wiki_input(part1),

}



end)



local modules = {}

modules'bit32' = require('bit32')

modules'string' = require('string')

modules'strict' = {}

modules'table' = require('table')

local function myrequire(name)

  if modulesname == nil then

    modulesname = true

    modulesname = (buildersname])(myrequire)

  end

  return modulesname

end

return myrequire('day25')

end)()