競プロ典型 90 問 71 日目 - Fuzzy Priority（★7）
import Control.Monad
import Data.Bool
import qualified Data.ByteString.Char8 as C
import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.PatriciaTree
import Data.List
import Data.Maybe
import Data.Sequence (Seq(..), (><))
import qualified Data.Sequence as Seq
main = ints >>= \[n,m,k] -> replicateM m ints >>= fmt . sol n k
ints = unfoldr (C.readInt . C.dropWhile (==' ')) <$> C.getLine
fmt = mapM_ (putStrLn . unwords . map show)
sol n k as = if length rs==k then map reverse rs else [[-1]]
where
g = mkUGraph [1..n] $ map (\[u,v] -> (u,v)) as :: Gr () ()
rs = dfs n k $ mkq k [] g (top g)
top = filter . ((0 ==) .) . indeg <*> nodes
perm v = [m:l++r | i <- [0..length v-1], let (l,m:r) = splitAt i v]
mkq k p g [] = Seq.fromList [([],p,g)]
mkq k p g v = Seq.fromList . map (,p,g) . take k $ perm v
dfs _ 0 _ = []
dfs _ _ Empty = []
dfs n k ((v,p,g) :<| q)
| length p==n = p:dfs n (k-1) q
| null v || isEmpty g = dfs n k q
| otherwise = case match (head v) g of
(Nothing,_) -> dfs n k q
(Just (_,_,_,s),g') -> dfs n k $ q' >< q
where
v' = filter ((==0) . indeg g') (map snd s) ++ tail v
p' = head v:p
q' = mkq (k-Seq.length q) p' g' v'
