import Data.List (sort)

nums :: [String]
nums = map show . filter (\x -> x < 10 || x `rem` 10 /= 0) $ [1..9] ++ [1001,1000..10]

numShiritori :: [String]
numShiritori = f nums
    where
      f [] = []
      f (x:xs) = x : f next
          where
            next = g xs []
            g [] _ = []
            g (y:ys) acc | last x == head y = y : reverse acc ++ ys
                         | otherwise = g ys (y:acc)

main :: IO ()
main = do
    print $ sort nums == sort numShiritori
    print $ isShiritori numShiritori
    putStrLn . unwords $ numShiritori

-- for debug
isShiritori :: [String] -> Bool
isShiritori [] = True
isShiritori [_] = True
isShiritori (x:y:ys) = last x == head y && isShiritori (y:ys)