{- Karol Samborski -}
module Main where
import Data.List
import Data.Array
type Edge = Int
data Vertex = Vertex { nr :: Int, edges :: [Edge], low :: Int }
type Bridge = (Int, Int)
findBridges :: Array Int Vertex -> [Bridge]
findBridges vs = foldr (\(i, v) acc ->
if low v == nr v
then (zip [i,i..] $ filter (\e -> low (newVs!e) /= low v) $ edges v) ++ acc
else acc) [] $ assocs newVs
where
newVs = dfsBridges [1] vs 1
dfsBridges :: [Int] -> Array Int Vertex -> Int -> Array Int Vertex
dfsBridges [] ar _ = ar
dfsBridges (v:vs) ar d = dfsArray // [(v, (dfsArray!v) { low = foldr (\e l ->
if (nr $ dfsArray!e) > (-1) && e /= (d-1) && (low $ dfsArray!e) < l
then (low $ dfsArray!e)
else l) d $ edges $ dfsArray!v})]
where
initArr = ar//[(v, (ar!v) {nr = d, low = d})]
stack = foldr (\e l ->
if (nr $ initArr!e) > (-1)
then l
else l ++ [e]) vs $ edges $ ar!v
dfsArray = dfsBridges stack initArr (d+1)
main :: IO ()
main = do
count <- (getLine >>= readIO) :: IO Int
v <- mapM (\i -> do
l <- (getLine >>= readIO) :: IO [Int]
return $ Vertex (-1) l (-1)) [1..count]
putStrLn $ show $ findBridges $ listArray (1,count) v