#!/usr/bin/env luajit
require("utils")
require("set")

local graph = {}
local lower = set()
for line in io.lines(arg[3]) do
	local a, b = unpack(split(line, "-"))
	local as, bs = graph[a] or {}, graph[b] or {}
	table.insert(as, b)
	table.insert(bs, a)
	if string.lower(a) == a then lower:add(a) end
	if string.lower(b) == b then lower:add(b) end
	graph[a] = as
	graph[b] = bs
end

local function backtrack(i, once)
	if i == "end" then
		return 1
	else
		local paths = 0
		for k, v in pairs(graph[i]) do
			if not lower:has(v) or not once:has(v) then
				once:add(v)
				paths = paths + backtrack(v, once)
				once:remove(v)
			end
		end
		return paths
	end
end

print(backtrack("start", set({"start"})))