TwoColors.hs

import Control.Applicative ((<$>))
import Data.List (partition)
import Data.Map (Map)
import qualified Data.Map as M

type Edge = [Int]

data Color = Red | Black deriving (Show, Eq)

type Paint = Map Int Color

isTwoColor :: [Int] -> [Edge] -> Bool
isTwoColor []     [] = True
isTwoColor (v:vs) edges = check vs edges M.empty

check :: [Int] -> [Edge] -> Paint -> Bool
check [] _ _ = True
check (v:vs) es p =
	case go v es $ M.insert v Black p of
		Nothing -> False
		Just (p', es') -> check vs es' p'

go :: Int -> [Edge] -> Paint -> Maybe (Paint, [Edge])
go v es p =
	let (adjEdges, another) = partition (elem v) es in
	let adj = map (head . filter (/= v)) adjEdges in
	let Just vc = M.lookup v p in
	let c = if vc == Black then Red else Black in
	if not $ all (\v -> M.lookup v p /= Just vc) adj
	then Nothing
	else
		let p' = foldl (\m v -> M.insert v c m) p adj in
		foldl (\acc v -> case acc of
				Nothing -> Nothing
				Just (p, es) -> go v es p
			) (Just (p', another)) adj

readNumList :: String -> [Int]
readNumList = map read . words
 
main :: IO ()
main = do
	[v, e] <- readNumList <$> getLine
	edges <- map readNumList <$> (sequence $ replicate e getLine)
	if isTwoColor [1..v] edges
	then putStrLn "YES"
	else putStrLn "NO"