content: {-# OPTIONS -fno-spec-constr-count #-}
  module Algo.AwShCC (awshcc) where
  
  import Data.Vector.Unboxed as V
  
  awshcc :: (Int, Vector Int, Vector Int) -> Vector Int
  {-# NOINLINE awshcc #-}
  awshcc (n, es1, es2) = concomp ds es1' es2'
      where
        ds = V.enumFromTo 0 (n-1) V.++ V.enumFromTo 0 (n-1)
        es1' = es1 V.++ es2
        es2' = es2 V.++ es1
  
        starCheck ds = V.backpermute st' gs
          where
            gs  = V.backpermute ds ds
            st  = V.zipWith (==) ds gs
            st' = V.update st . V.filter (not . snd)
                              $ V.zip gs st
  
        concomp ds es1 es2
          | V.and (starCheck ds'') = ds''
          | otherwise              = concomp (V.backpermute ds'' ds'') es1 es2
          where
            ds'  = V.update ds
                 . V.map (\(di, dj, gi) -> (di, dj))
                 . V.filter (\(di, dj, gi) -> gi == di && di > dj)
                 $ V.zip3 (V.backpermute ds es1)
                          (V.backpermute ds es2)
                          (V.backpermute ds (V.backpermute ds es1))
  
            ds'' = V.update ds'
                 . V.map (\(di, dj, st) -> (di, dj))
                 . V.filter (\(di, dj, st) -> st && di /= dj)
                 $ V.zip3 (V.backpermute ds' es1)
                          (V.backpermute ds' es2)
                          (V.backpermute (starCheck ds') es1)
  
  