https://codeiq.jp/ace/yuki_hiroshi/q411 ダイクストラで。

deepest.hs

import Control.Applicative((<$>))
import Data.List (intersperse, foldl')
import qualified Data.Map as M
import Network.HTTP (getResponseBody, simpleHTTP, getRequest)
import System.Posix.Unistd (nanosleep)

type Id     = String
data Star   = Star { cost :: Int, stars :: [Id], routes :: [Id] } deriving (Show, Eq)
type Galaxy = M.Map Id Star

start, deep, deeper, deepest :: Id
start   = "5426528869786"
deep    = "4363616111476"
deeper  = "5092488161056"
deepest = "8838746292440"

main :: IO ()
main = putStrLn $ solve api
  where
    solve g = concat . intersperse "," $ start2deep ++ deep2deeper ++ deeper2deepest
      where
        start2deep     = init . getRoute deep    $ dijkstra g start
        deep2deeper    = init . getRoute deeper  $ dijkstra g deep
        deeper2deepest = getRoute deepest $ dijkstra g deeper
        getRoute goal glx = case M.lookup goal glx of
                                Nothing            -> error "Oops!"
                                Just (Star _ _ rs) -> reverse rs

dijkstra :: Galaxy -> Id -> Galaxy
dijkstra galaxy start' = go (update start' 1 [] galaxy) start'
  where
    go :: Galaxy -> Id -> Galaxy
    go g key = case M.lookup  key g of
        Nothing               -> g
        Just (Star cst xs rs) -> let g' = foldl' (walk cst rs) g xs in
                                  if g' == g
                                  then g
                                  else foldl' go g' xs

    walk :: Int -> [Id] -> Galaxy -> Id -> Galaxy
    walk cst rs g sid = update sid (cst + 1) rs g

    update :: Id -> Int -> [Id] -> Galaxy -> Galaxy
    update key val rs = M.adjust up key
      where
        up star@(Star v xs _)
            | val < v   = Star val xs (key:rs)
            | otherwise = star

-- API を呼んで、星のグラフを作成する.
-- 毎回 API を呼ぶと時間がかかるので、あらかじめグラフを作成し、それを記録しておく。
-- 記録したグラフをもとに経路を探索する（実装する）。
visit :: Galaxy -> Id -> [Id] -> IO Galaxy
visit galaxy _   []            = return galaxy
visit galaxy dst (starId:sids) = case M.lookupIndex starId galaxy of
    Just _  -> visit galaxy dst sids
    Nothing -> do
        starIds <- directStarIds starId
        let galaxy' = M.insert starId (Star maxBound starIds []) galaxy
        galaxy'' <- visit galaxy' dst sids
        visit galaxy'' dst starIds

initGalaxy :: Galaxy
initGalaxy = M.empty

directStarIds :: Id -> IO [Id]
directStarIds sid = do
    black <- callApi $ buildUrl sid 10000 -- nthを大きくしても0を返さない星があるので、
    if black /= "0"                       -- nth=10000の結果が0でない場合は飛ばす
    then return []
    else tell sid 0

buildUrl :: String -> Int -> String
buildUrl sid nth = concat [baseURL, "?id=", sid, "&nth=", show nth]

baseURL :: String
baseURL = "http://133.242.134.37/deepest.cgi"

tell :: String -> Int -> IO [Id]
tell sid n = do
    nid <- callApi $ buildUrl sid n
    if nid == "0"
    then return []
    else do wait
            nids <- tell sid (n + 1)
            return (nid:nids)

callApi :: String -> IO String
callApi url = do
    rsp  <- simpleHTTP $ getRequest url
    trim <$> getResponseBody rsp

trim :: String -> String
trim = head . lines

wait :: IO ()
wait = nanosleep 500000000



-- これがグラフ
api :: Galaxy
api = M.fromList [("1074912512567",Star {cost = maxBound, stars = ["7560374248806"], routes = []}),("1126539747818",Star {cost = maxBound, stars = ["3536542280812","4498551666547","7934869824134"], routes = []}),("1286793284768",Star {cost = maxBound, stars = ["2278847430214","2979009521142","4656064657053","5813746423067","6178493999671","7797971735921","8479078158931"], routes = []}),("1387294622447",Star {cost = maxBound, stars = ["2152647356070","4775196002726","5596295380961","5848253839570","6040500266078","7170473222416","8682011082922"], routes = []}),("1393535186516",Star {cost = maxBound, stars = ["1969677761104","3736649321407","4981224125121","8742972189444"], routes = []}),("1460668290338",Star {cost = maxBound, stars = ["2812280975542","3070747769765","3426517176360","3943178099168","7116209295800","8701256641199"], routes = []}),("1538887501806",Star {cost = maxBound, stars = ["1393535186516","2951941120697","3736649321407","5211818698514","5813746423067","6023249450084","7401422935060"], routes = []}),("1560964630314",Star {cost = maxBound, stars = ["2874753037631","4491504900204","5226891391388","5256084349572","5985346038182","6912947983983","7706339201843"], routes = []}),("1563577571047",Star {cost = maxBound, stars = ["8742972189444"], routes = []}),("1582015354379",Star {cost = maxBound, stars = ["1757786369613","1969677761104","4411233758267","5211818698514","5471056644598","7892247098840"], routes = []}),("1582053847804",Star {cost = maxBound, stars = ["2223936654310","4940548870566","5341666331568","6040500266078","8025149145454","8636102321011"], routes = []}),("1588698186896",Star {cost = maxBound, stars = ["1126539747818","1286793284768","1538887501806","4411233758267","4656064657053","5471056644598"], routes = []}),("1649317345636",Star {cost = maxBound, stars = ["1538887501806","1757786369613","2864141700776","5873652513502","8244481309445","8986753372139"], routes = []}),("1709053023065",Star {cost = maxBound, stars = ["2714053169768"], routes = []}),("1757786369613",Star {cost = maxBound, stars = ["1538887501806","2979009521142","4411233758267","5485131078541"], routes = []}),("1814964223463",Star {cost = maxBound, stars = [], routes = []}),("1843019516033",Star {cost = maxBound, stars = ["5092488161056"], routes = []}),("1861908423450",Star {cost = maxBound, stars = ["1582053847804","3545866022750","5279254700468","7194628242299","8225271457185"], routes = []}),("1969677761104",Star {cost = maxBound, stars = ["1286793284768","2864141700776","3971331745645","5174811483802","8986753372139"], routes = []}),("2109165486888",Star {cost = maxBound, stars = ["1582053847804","2223936654310","3101910152403","3426517176360","3954809916077","4946412662661","5260999957124","6199888663851","7652884912454","7758274483738","8573279739883"], routes = []}),("2114116223711",Star {cost = maxBound, stars = ["5609234254073","7713050646130"], routes = []}),("2127255330716",Star {cost = maxBound, stars = ["4494366137783","5596295380961","5692390052367","6040500266078","6931349063153","8179247968273"], routes = []}),("2152647356070",Star {cost = maxBound, stars = ["1582053847804","2994428026714","4597865188910","7652884912454","8345370958267","8978032168895"], routes = []}),("2223936654310",Star {cost = maxBound, stars = ["2109165486888","2292547528724","2689904713261","3575202947166","3943178099168","5717371807428","7758274483738","8025149145454"], routes = []}),("2274178593884",Star {cost = maxBound, stars = ["2889377221366"], routes = []}),("2278847430214",Star {cost = maxBound, stars = ["1126539747818","1757786369613","5702278445116","7782150475311","8188288894326","8735695204612"], routes = []}),("2292547528724",Star {cost = maxBound, stars = ["2127255330716","2994428026714","4787665361584","5341666331568","5692390052367","7194628242299","7840395069634","8033311672835","8179247968273"], routes = []}),("2296982965872",Star {cost = maxBound, stars = ["1286793284768","5099100039591","5702278445116","8188288894326","8244481309445"], routes = []}),("2301263421283",Star {cost = maxBound, stars = ["1560964630314","1861908423450","2223936654310","2652448977671","2994428026714","4597865188910","4940548870566","6931349063153","8573279739883"], routes = []}),("2313824135439",Star {cost = maxBound, stars = ["2874753037631","4442110767899","4940548870566","5260999957124"], routes = []}),("2438979188297",Star {cost = maxBound, stars = ["1387294622447","3575202947166","4491504900204","5985346038182"], routes = []}),("2484466449149",Star {cost = maxBound, stars = ["4326837688991"], routes = []}),("2547413633555",Star {cost = maxBound, stars = ["2966922227746"], routes = []}),("2615115005762",Star {cost = maxBound, stars = ["3492704769369"], routes = []}),("2652448977671",Star {cost = maxBound, stars = ["1387294622447","3288980428753","3545866022750","3840068516051","7840395069634","8682011082922","8741714209435"], routes = []}),("2689904713261",Star {cost = maxBound, stars = ["1460668290338","2301263421283","3288980428753","6762287044283","6925571750184","7706339201843","8225271457185"], routes = []}),("2714053169768",Star {cost = maxBound, stars = ["4808682723030"], routes = []}),("2718120095809",Star {cost = maxBound, stars = ["1460668290338","4491504900204","4787665361584","5102464619742","5692390052367","6159786607508","6707581077767","6762287044283","8108466497204","8573279739883","8701256641199"], routes = []}),("2780144620728",Star {cost = maxBound, stars = ["3031196364476","3575202947166","4946412662661","5576554716124","7230764147984","7840395069634","8784346813978"], routes = []}),("2782215861852",Star {cost = maxBound, stars = ["2152647356070","2812280975542","3426517176360","3545866022750","4775196002726","8225271457185"], routes = []}),("2812280975542",Star {cost = maxBound, stars = ["1460668290338","4940548870566","5985346038182","6085641567012","6199888663851","7706339201843"], routes = []}),("2864141700776",Star {cost = maxBound, stars = ["1126539747818","1393535186516","1757786369613","3736649321407","5099100039591","5211818698514","5451824622148","7401422935060","8564585174926","8735695204612"], routes = []}),("2874753037631",Star {cost = maxBound, stars = ["3070747769765","3101910152403","4775196002726","6159786607508","8978032168895"], routes = []}),("2889377221366",Star {cost = maxBound, stars = ["4719403867330"], routes = []}),("2951941120697",Star {cost = maxBound, stars = ["3020468649487","3065937285535","3437245100188","3736649321407","7782150475311","7892247098840","8054128267676","8244481309445"], routes = []}),("2966922227746",Star {cost = maxBound, stars = ["1843019516033"], routes = []}),("2970040126310",Star {cost = maxBound, stars = ["6218636660558"], routes = []}),("2979009521142",Star {cost = maxBound, stars = ["1538887501806","3020468649487","3437245100188","5174811483802","5451824622148","5873652513502","6178493999671","7892247098840"], routes = []}),("2994428026714",Star {cost = maxBound, stars = ["2874753037631","3031196364476","4946412662661","8033311672835","8225271457185","8345370958267","8741714209435","8978032168895"], routes = []}),("3014332099928",Star {cost = maxBound, stars = ["4363616111476","8401992270535"], routes = []}),("3020468649487",Star {cost = maxBound, stars = ["1126539747818","1286793284768","1538887501806","5813746423067","8054128267676"], routes = []}),("3020606866347",Star {cost = maxBound, stars = ["1460668290338","5985346038182","6870921135953","7840395069634"], routes = []}),("3031196364476",Star {cost = maxBound, stars = ["1387294622447","1460668290338","1560964630314","4205606644588","5279254700468","5591596393385","6201473389311","6912947983983","6925571750184","7652884912454","8108466497204","8784346813978"], routes = []}),("3065937285535",Star {cost = maxBound, stars = ["1286793284768","2296982965872","3437245100188","5813746423067","8054128267676","8188288894326","8433634935614"], routes = []}),("3070747769765",Star {cost = maxBound, stars = ["2292547528724","2313824135439","2812280975542","6085641567012","6146124596038"], routes = []}),("3101910152403",Star {cost = maxBound, stars = ["2292547528724","2652448977671","3545866022750","5596295380961","5717371807428","5985346038182","6925571750184","8025149145454","8682011082922"], routes = []}),("3178207859393",Star {cost = maxBound, stars = ["5099100039591","5174811483802","5451824622148","8735695204612"], routes = []}),("3288980428753",Star {cost = maxBound, stars = ["1861908423450","2718120095809","2780144620728","3031196364476","3070747769765","4205606644588","5102464619742","6146124596038"], routes = []}),("3351698485723",Star {cost = maxBound, stars = [], routes = []}),("3426517176360",Star {cost = maxBound, stars = ["3101910152403","3840068516051","4205606644588","7706339201843","8701256641199"], routes = []}),("3437245100188",Star {cost = maxBound, stars = ["1538887501806","3065937285535","3459654931377","4656064657053","5702278445116","5813746423067","5833671447983","6137149535463","8279056819547","8279347398297"], routes = []}),("3459654931377",Star {cost = maxBound, stars = ["1126539747818","1393535186516","4498551666547","7782150475311","7797971735921","7892247098840","8244481309445"], routes = []}),("3492704769369",Star {cost = maxBound, stars = ["6101275938556"], routes = []}),("3536542280812",Star {cost = maxBound, stars = ["1126539747818","1757786369613","2979009521142","5099100039591","6178493999671"], routes = []}),("3545866022750",Star {cost = maxBound, stars = ["3020606866347","3954809916077","4494366137783","5717371807428","6199888663851","6201473389311","6449164628142","7116209295800"], routes = []}),("3575202947166",Star {cost = maxBound, stars = ["1582053847804","2718120095809","3070747769765","5260999957124","6085641567012","7194628242299","7652884912454","8787239992833"], routes = []}),("3736649321407",Star {cost = maxBound, stars = ["1393535186516","1588698186896"], routes = []}),("3753634561927",Star {cost = maxBound, stars = [], routes = []}),("3840068516051",Star {cost = maxBound, stars = ["2313824135439","2812280975542","3031196364476","4205606644588","8033311672835","8682011082922","8787239992833"], routes = []}),("3876548341627",Star {cost = maxBound, stars = ["1588698186896","2864141700776","7014829010728","8279347398297","8742972189444"], routes = []}),("3943178099168",Star {cost = maxBound, stars = ["2301263421283","2874753037631","4494366137783","5102464619742","5576554716124","6146124596038","6449164628142","6912947983983","7758274483738","8025149145454"], routes = []}),("3954809916077",Star {cost = maxBound, stars = ["2438979188297","2874753037631","3070747769765","3288980428753","5226891391388","6707581077767","6912947983983","8179247968273","8787239992833"], routes = []}),("3971331745645",Star {cost = maxBound, stars = ["1588698186896","2979009521142","3178207859393","5485131078541","5813746423067","7934869824134","8188288894326","8244481309445","8735695204612","8986753372139"], routes = []}),("4002483274237",Star {cost = maxBound, stars = ["1286793284768","3178207859393","3736649321407","4656064657053","6137149535463","8479078158931"], routes = []}),("4113418725800",Star {cost = maxBound, stars = [], routes = []}),("4117233359501",Star {cost = maxBound, stars = ["2438979188297","4940548870566","6931349063153","7706339201843"], routes = []}),("4205606644588",Star {cost = maxBound, stars = ["2313824135439","3288980428753","4442110767899","5256084349572","5848253839570","6931349063153","7652884912454"], routes = []}),("4217007177539",Star {cost = maxBound, stars = ["2970040126310"], routes = []}),("4326837688991",Star {cost = maxBound, stars = ["5622625817530","6021351385219","7198714263165"], routes = []}),("4363616111476",Star {cost = maxBound, stars = ["2615115005762"], routes = []}),("4404687427717",Star {cost = maxBound, stars = ["5471056644598","7782150475311"], routes = []}),("4411233758267",Star {cost = maxBound, stars = ["3178207859393","3876548341627","6137149535463","7782150475311"], routes = []}),("4442110767899",Star {cost = maxBound, stars = ["2782215861852","2812280975542","4775196002726","5256084349572","5260999957124","5692390052367","7116209295800","7170473222416"], routes = []}),("4491504900204",Star {cost = maxBound, stars = ["1387294622447","2223936654310","6159786607508","6870921135953","7116209295800","8784346813978","8787239992833"], routes = []}),("4494366137783",Star {cost = maxBound, stars = ["2127255330716","2780144620728","4946412662661","5576554716124","5717371807428","8033311672835","8526665430645","8573279739883"], routes = []}),("4498551666547",Star {cost = maxBound, stars = ["1582015354379","1649317345636","3020468649487","3736649321407","4404687427717","6023249450084","6730551897632","7934869824134","8279056819547","8279347398297"], routes = []}),("4571265613335",Star {cost = maxBound, stars = [], routes = []}),("4597865188910",Star {cost = maxBound, stars = ["2223936654310","2292547528724","2438979188297","2780144620728","3575202947166","5692390052367","6912947983983","7116209295800","7706339201843","8025149145454","8033311672835","8682011082922"], routes = []}),("4656064657053",Star {cost = maxBound, stars = ["2951941120697","3065937285535","4411233758267","5451824622148","8279347398297","8433634935614","8564585174926"], routes = []}),("4656383184179",Star {cost = maxBound, stars = [], routes = []}),("4719403867330",Star {cost = maxBound, stars = ["1709053023065","8254591808673"], routes = []}),("4775196002726",Star {cost = maxBound, stars = ["3351698485723","4494366137783","5596295380961","5717371807428","6870921135953","7684149340544","7840395069634","8262133957338","8784346813978"], routes = []}),("4787665361584",Star {cost = maxBound, stars = ["3101910152403","3288980428753","7116209295800","8033311672835","8636102321011"], routes = []}),("4808682723030",Star {cost = maxBound, stars = [], routes = []}),("4940548870566",Star {cost = maxBound, stars = ["2313824135439","5576554716124","7230764147984","8033311672835","8573279739883"], routes = []}),("4945726804434",Star {cost = maxBound, stars = ["2313824135439","2874753037631","4494366137783","6870921135953","7194628242299"], routes = []}),("4946412662661",Star {cost = maxBound, stars = ["1560964630314","2438979188297","2782215861852","3840068516051","8636102321011","8978032168895"], routes = []}),("4950294170041",Star {cost = maxBound, stars = ["5792719602457","6493203887111"], routes = []}),("4981224125121",Star {cost = maxBound, stars = ["3736649321407","3971331745645","5211818698514","7322686465928","8986753372139"], routes = []}),("5063705301914",Star {cost = maxBound, stars = ["1286793284768","3437245100188","4404687427717"], routes = []}),("5092488161056",Star {cost = maxBound, stars = ["8250347815782"], routes = []}),("5099100039591",Star {cost = maxBound, stars = ["3020468649487","3178207859393","3736649321407","5471056644598","8054128267676"], routes = []}),("5102464619742",Star {cost = maxBound, stars = ["2689904713261","4117233359501","6159786607508","8784346813978","8978032168895"], routes = []}),("5174811483802",Star {cost = maxBound, stars = ["1538887501806","1582015354379","4656064657053","4981224125121","5211818698514","5873652513502","7934869824134","8433634935614","8986753372139"], routes = []}),("5211818698514",Star {cost = maxBound, stars = ["1969677761104","3065937285535","3178207859393","4656064657053","5451824622148","5873652513502","8479078158931"], routes = []}),("5226891391388",Star {cost = maxBound, stars = ["2127255330716","3288980428753","4442110767899","5102464619742","6449164628142","7116209295800","7706339201843","7840395069634","8784346813978"], routes = []}),("5256084349572",Star {cost = maxBound, stars = ["2109165486888","3288980428753","3575202947166","3943178099168","4117233359501","6201473389311","7706339201843","8573279739883","8682011082922"], routes = []}),("5260999957124",Star {cost = maxBound, stars = ["2780144620728","4491504900204","4597865188910","6159786607508","8225271457185"], routes = []}),("5279254700468",Star {cost = maxBound, stars = ["7116209295800","7652884912454"], routes = []}),("5341666331568",Star {cost = maxBound, stars = ["2301263421283","4775196002726","5576554716124","7170473222416","8526665430645"], routes = []}),("5426528869786",Star {cost = maxBound, stars = ["2484466449149"], routes = []}),("5451824622148",Star {cost = maxBound, stars = ["5702278445116","7401422935060","7782150475311","7797971735921"], routes = []}),("5471056644598",Star {cost = maxBound, stars = ["2278847430214","3065937285535","3876548341627","5211818698514","5451824622148","6023249450084","6178493999671","6730551897632","7892247098840"], routes = []}),("5485131078541",Star {cost = maxBound, stars = ["1538887501806","1582015354379","3876548341627","7401422935060","8279056819547"], routes = []}),("5576554716124",Star {cost = maxBound, stars = ["2152647356070","5848253839570","6159786607508","7194628242299","8741714209435"], routes = []}),("5591596393385",Star {cost = maxBound, stars = ["5865952095146"], routes = []}),("5596295380961",Star {cost = maxBound, stars = ["1387294622447","2874753037631","4494366137783","5102464619742","5260999957124","6040500266078","6085641567012","6201473389311","6707581077767","8784346813978"], routes = []}),("5609234254073",Star {cost = maxBound, stars = ["4808682723030","8401992270535"], routes = []}),("5622625817530",Star {cost = maxBound, stars = ["2274178593884","2714053169768","6248392538888"], routes = []}),("5692390052367",Star {cost = maxBound, stars = ["1861908423450","3545866022750","7170473222416","7840395069634","8526665430645"], routes = []}),("5702278445116",Star {cost = maxBound, stars = ["1126539747818","1538887501806","1757786369613","2864141700776","3459654931377"], routes = []}),("5717371807428",Star {cost = maxBound, stars = ["1582053847804","2109165486888","3101910152403","4491504900204","4946412662661","5226891391388","6040500266078","6707581077767","8573279739883"], routes = []}),("5754575559250",Star {cost = maxBound, stars = ["5609234254073"], routes = []}),("5792719602457",Star {cost = maxBound, stars = ["4571265613335","7713050646130"], routes = []}),("5793542169547",Star {cost = maxBound, stars = ["4217007177539"], routes = []}),("5813482662518",Star {cost = maxBound, stars = ["2547413633555"], routes = []}),("5813746423067",Star {cost = maxBound, stars = ["1538887501806","2979009521142","3437245100188","3459654931377"], routes = []}),("5833671447983",Star {cost = maxBound, stars = ["6714942513619"], routes = []}),("5848253839570",Star {cost = maxBound, stars = ["2994428026714","4946412662661","5102464619742","6707581077767","7170473222416","8701256641199"], routes = []}),("5865952095146",Star {cost = maxBound, stars = ["8838746292440"], routes = []}),("5873652513502",Star {cost = maxBound, stars = ["2296982965872","3536542280812","5813746423067","8433634935614"], routes = []}),("5930121741023",Star {cost = maxBound, stars = [], routes = []}),("5985346038182",Star {cost = maxBound, stars = ["1387294622447","2109165486888","2780144620728","2994428026714","5692390052367","7758274483738","8741714209435"], routes = []}),("6021351385219",Star {cost = maxBound, stars = ["2114116223711","3753634561927","5930121741023","6159521237181","8401992270535","8814668496374"], routes = []}),("6023249450084",Star {cost = maxBound, stars = ["1582015354379","1649317345636","1969677761104","3020468649487","4002483274237","4656064657053","7014829010728","7401422935060"], routes = []}),("6040500266078",Star {cost = maxBound, stars = ["1861908423450","2109165486888","5717371807428","6707581077767","7758274483738"], routes = []}),("6085641567012",Star {cost = maxBound, stars = ["1861908423450","2994428026714","3840068516051","3943178099168","3954809916077","4940548870566","5596295380961","5985346038182","6931349063153"], routes = []}),("6101275938556",Star {cost = maxBound, stars = ["5793542169547"], routes = []}),("6137149535463",Star {cost = maxBound, stars = ["1393535186516","2278847430214","2864141700776","2979009521142","3459654931377","3971331745645","5485131078541","7782150475311","7892247098840","7934869824134","8433634935614"], routes = []}),("6146124596038",Star {cost = maxBound, stars = ["3020606866347","3031196364476","3943178099168","5985346038182","8701256641199"], routes = []}),("6159521237181",Star {cost = maxBound, stars = ["5930121741023","6248392538888"], routes = []}),("6159786607508",Star {cost = maxBound, stars = ["2109165486888","3943178099168","8108466497204"], routes = []}),("6178493999671",Star {cost = maxBound, stars = ["2296982965872","4411233758267","5485131078541","7014829010728","8054128267676","8188288894326","8742972189444"], routes = []}),("6199888663851",Star {cost = maxBound, stars = ["4597865188910","6931349063153","7116209295800","7194628242299","8573279739883"], routes = []}),("6201473389311",Star {cost = maxBound, stars = ["2313824135439","3954809916077","4205606644588","4597865188910","5341666331568","5576554716124","6146124596038","6199888663851","6762287044283","8179247968273","8345370958267","8526665430645"], routes = []}),("6218636660558",Star {cost = maxBound, stars = ["1563577571047"], routes = []}),("6248392538888",Star {cost = maxBound, stars = ["4950294170041","5792719602457"], routes = []}),("6449164628142",Star {cost = maxBound, stars = ["2994428026714","3288980428753","4597865188910","4945726804434","6085641567012","8225271457185","8978032168895"], routes = []}),("6493203887111",Star {cost = maxBound, stars = ["3014332099928"], routes = []}),("6707581077767",Star {cost = maxBound, stars = ["1582053847804","2438979188297","2652448977671","2718120095809","3020606866347","3031196364476","3954809916077","4205606644588","5102464619742","5256084349572","5576554716124","5717371807428","6925571750184"], routes = []}),("6714942513619",Star {cost = maxBound, stars = ["7049674030681"], routes = []}),("6730551897632",Star {cost = maxBound, stars = ["3178207859393","5211818698514","7797971735921","8279347398297"], routes = []}),("6762287044283",Star {cost = maxBound, stars = ["2127255330716","2874753037631","3101910152403","4787665361584","5717371807428","6199888663851","6925571750184","8526665430645"], routes = []}),("6870921135953",Star {cost = maxBound, stars = ["5102464619742","5717371807428","6931349063153","8108466497204"], routes = []}),("6912947983983",Star {cost = maxBound, stars = ["2652448977671","3840068516051","4494366137783","5985346038182","6040500266078","6870921135953","7706339201843"], routes = []}),("6925571750184",Star {cost = maxBound, stars = ["1560964630314","1582053847804","2292547528724","3545866022750","7194628242299","7706339201843","8682011082922","8701256641199"], routes = []}),("6931349063153",Star {cost = maxBound, stars = ["5279254700468","5341666331568","5848253839570"], routes = []}),("7014829010728",Star {cost = maxBound, stars = ["2278847430214","2979009521142","3971331745645","4411233758267","6178493999671","7322686465928","8244481309445","8279056819547","8986753372139"], routes = []}),("7049674030681",Star {cost = maxBound, stars = ["5813482662518"], routes = []}),("7116209295800",Star {cost = maxBound, stars = ["1861908423450","2292547528724","2812280975542","2874753037631","4597865188910","5226891391388","5256084349572","6159786607508","6449164628142","6870921135953","7652884912454","8784346813978"], routes = []}),("7170473222416",Star {cost = maxBound, stars = ["2127255330716","2652448977671","4491504900204","4494366137783","5279254700468","8033311672835"], routes = []}),("7194628242299",Star {cost = maxBound, stars = ["1560964630314","2812280975542","4117233359501","4491504900204","4787665361584","6762287044283","6912947983983","7706339201843","8701256641199"], routes = []}),("7198714263165",Star {cost = maxBound, stars = [], routes = []}),("7230764147984",Star {cost = maxBound, stars = ["2223936654310","2438979188297","2812280975542","3288980428753","3545866022750","5102464619742","5226891391388","5256084349572","5576554716124","6159786607508","7840395069634","8701256641199"], routes = []}),("7322686465928",Star {cost = maxBound, stars = ["3536542280812","5702278445116","8479078158931"], routes = []}),("7401422935060",Star {cost = maxBound, stars = ["1969677761104","3178207859393","4656064657053","4981224125121","5063705301914","5099100039591"], routes = []}),("7560374248806",Star {cost = maxBound, stars = ["8217940346560"], routes = []}),("7652884912454",Star {cost = maxBound, stars = ["2223936654310","3101910152403","5279254700468","8526665430645","8636102321011"], routes = []}),("7684149340544",Star {cost = maxBound, stars = [], routes = []}),("7706339201843",Star {cost = maxBound, stars = ["2292547528724","2301263421283","2812280975542","6159786607508","8784346813978"], routes = []}),("7713050646130",Star {cost = maxBound, stars = ["3014332099928","6493203887111"], routes = []}),("7758274483738",Star {cost = maxBound, stars = ["4597865188910","4946412662661","6085641567012","6159786607508","8682011082922"], routes = []}),("7782150475311",Star {cost = maxBound, stars = ["1969677761104","2864141700776","4002483274237","4498551666547","5813746423067","8054128267676","8244481309445"], routes = []}),("7797971735921",Star {cost = maxBound, stars = ["3971331745645","5099100039591","7014829010728","7322686465928","7782150475311","8735695204612"], routes = []}),("7840395069634",Star {cost = maxBound, stars = ["2152647356070","2301263421283","4945726804434","5279254700468","6925571750184","8179247968273"], routes = []}),("7892247098840",Star {cost = maxBound, stars = ["1757786369613","2864141700776","4656064657053","5873652513502","7014829010728","7401422935060","8479078158931"], routes = []}),("7934869824134",Star {cost = maxBound, stars = ["1969677761104","2278847430214","3971331745645","4404687427717","5063705301914","5211818698514","5451824622148","6730551897632","7782150475311"], routes = []}),("8025149145454",Star {cost = maxBound, stars = ["1460668290338","2223936654310","2313824135439","2652448977671","2994428026714","3840068516051","4205606644588","4442110767899","4940548870566","7840395069634","8345370958267"], routes = []}),("8033311672835",Star {cost = maxBound, stars = ["1861908423450","4946412662661","5692390052367","6762287044283","7194628242299"], routes = []}),("8054128267676",Star {cost = maxBound, stars = ["2864141700776","3020468649487","3065937285535","7401422935060"], routes = []}),("8108466497204",Star {cost = maxBound, stars = ["2994428026714","5226891391388","5260999957124","5279254700468","5341666331568","6201473389311","6449164628142","6912947983983","8636102321011"], routes = []}),("8179247968273",Star {cost = maxBound, stars = ["3426517176360","3545866022750","3943178099168","4442110767899","5226891391388","5341666331568","6040500266078","8033311672835","8573279739883","8787239992833"], routes = []}),("8188288894326",Star {cost = maxBound, stars = ["2296982965872","2864141700776","3459654931377","5471056644598","7401422935060","7797971735921"], routes = []}),("8217940346560",Star {cost = maxBound, stars = ["6159521237181"], routes = []}),("8225271457185",Star {cost = maxBound, stars = ["2152647356070","2301263421283","2313824135439","2782215861852","3545866022750","3575202947166","4946412662661","5260999957124","5279254700468","5576554716124","8179247968273","8682011082922"], routes = []}),("8244481309445",Star {cost = maxBound, stars = ["1126539747818","1286793284768","3459654931377","7782150475311","8279056819547"], routes = []}),("8250347815782",Star {cost = maxBound, stars = ["4775196002726"], routes = []}),("8254591808673",Star {cost = maxBound, stars = ["5754575559250","8401992270535"], routes = []}),("8262133957338",Star {cost = maxBound, stars = [], routes = []}),("8279056819547",Star {cost = maxBound, stars = ["1538887501806","1588698186896","2979009521142","3178207859393","3536542280812","4498551666547","6178493999671","7782150475311","7892247098840","8054128267676","8279347398297"], routes = []}),("8279347398297",Star {cost = maxBound, stars = ["3536542280812","5813746423067","8564585174926"], routes = []}),("8345370958267",Star {cost = maxBound, stars = ["3288980428753","3545866022750","3840068516051","4442110767899","6146124596038","6925571750184","6931349063153","8787239992833"], routes = []}),("8401992270535",Star {cost = maxBound, stars = ["5792719602457","8931131112829"], routes = []}),("8433634935614",Star {cost = maxBound, stars = ["1588698186896","2864141700776","4981224125121","8564585174926"], routes = []}),("8479078158931",Star {cost = maxBound, stars = ["2296982965872","3736649321407","5174811483802","5485131078541","6178493999671","8244481309445","8433634935614","8986753372139"], routes = []}),("8526665430645",Star {cost = maxBound, stars = ["1387294622447","2127255330716","2780144620728","4494366137783","4946412662661","5576554716124","7116209295800","7170473222416","7194628242299","8108466497204","8179247968273"], routes = []}),("8564585174926",Star {cost = maxBound, stars = ["1582015354379","1588698186896","1757786369613","5873652513502","6730551897632"], routes = []}),("8573279739883",Star {cost = maxBound, stars = ["2109165486888","2718120095809","2874753037631","6912947983983","8025149145454"], routes = []}),("8636102321011",Star {cost = maxBound, stars = ["1582053847804","3288980428753","6201473389311","6762287044283","7230764147984","8025149145454","8179247968273","8345370958267"], routes = []}),("8682011082922",Star {cost = maxBound, stars = ["2292547528724","2301263421283","2438979188297","2994428026714","3020606866347","4775196002726","6762287044283","6912947983983","8225271457185"], routes = []}),("8701256641199",Star {cost = maxBound, stars = ["2127255330716","3288980428753","3840068516051","4940548870566","5341666331568","6925571750184","7706339201843","8025149145454","8682011082922"], routes = []}),("8735695204612",Star {cost = maxBound, stars = ["1649317345636","3020468649487","4002483274237","4498551666547","5174811483802","6023249450084","7782150475311","8564585174926"], routes = []}),("8741714209435",Star {cost = maxBound, stars = ["1582053847804","2780144620728","6199888663851","8787239992833"], routes = []}),("8742972189444",Star {cost = maxBound, stars = ["1393535186516","1814964223463","3971331745645","4411233758267","4656383184179","7014829010728","8279056819547","8433634935614"], routes = []}),("8784346813978",Star {cost = maxBound, stars = ["2718120095809","3288980428753","4787665361584","8636102321011"], routes = []}),("8787239992833",Star {cost = maxBound, stars = ["1460668290338","2127255330716","2313824135439","3288980428753","3954809916077","4117233359501","4205606644588","6762287044283","6925571750184","7230764147984"], routes = []}),("8814668496374",Star {cost = maxBound, stars = ["1074912512567"], routes = []}),("8838746292440",Star {cost = maxBound, stars = [], routes = []}),("8931131112829",Star {cost = maxBound, stars = ["4113418725800"], routes = []}),("8978032168895",Star {cost = maxBound, stars = ["2292547528724","2313824135439","2438979188297","3101910152403","3426517176360","3545866022750","4775196002726","4946412662661","5848253839570","8108466497204"], routes = []}),("8986753372139",Star {cost = maxBound, stars = ["2979009521142","4498551666547","6137149535463","6730551897632","8279056819547"], routes = []})]