import Ix
import Array

-- standardni pole

bucketSort::Ix a => [a]->[a]
bucketSort xs = concat (elems arr)
  where
    l = minimum xs
    h = maximum xs
    arr = accumArray (flip (:)) [] (l, h) [(x,x)| x <- xs]

-- lina v prvcich (ale ne v indexech)

vzdalenost::String->String->Int
vzdalenost s1 s2 = vzd ! (l1, l2)
  where
    l1 = length s1
    l2 = length s2
    sa1 = array (1, l1) $ zip [1..] s1
    sa2 = array (1, l2) $ zip [1..] s2
    vzd = array ((0,0),(l1,l2)) $
            [((0, x), x) | x <- [0..l2]] ++
            [((x, 0), x) | x <- [1..l1]] ++
            [((c1, c2), vzdal c1 c2) | c1 <- [1..l1], c2 <- [1..l2]]
    vzdal c1 c2
      | sa1 ! c1 == sa2 ! c2 = vzd ! (c1 - 1, c2 - 1)
      | otherwise = 1 + ((vzd ! (c1 - 1, c2 - 1)) `min` (vzd ! (c1, c2 - 1)) `min` (vzd ! (c1 - 1, c2)))

-- zmena byt jen jednoho prvku vynucuje zkopirovani pole

type Vertex = Int
type Graph = Array Vertex [Vertex]
type Marks = Array Vertex Bool

data Tree a = Node a [Tree a] deriving (Show)

emptyMarks::Graph->Marks
emptyMarks g = accumArray undefined False (bounds g) []

dfs::Graph->[Vertex]->[Tree Vertex]
dfs g q = snd $ pruneForest (emptyMarks g) (map (search g) q)

search::Graph->Vertex->Tree Vertex
search g v = Node v $ map (search g) (g ! v)

pruneForest::Marks->[Tree Vertex]->(Marks, [Tree Vertex])
pruneForest m [] = (m, [])
pruneForest m (Node v s : t)
  | m ! v = pruneForest m t
  | otherwise = let (m', s') = pruneForest (m // [(v,True)]) s
                    (m'', t') = pruneForest m' t in
                  (m'', Node v s' : t')

-- problem -- kvadraticke