
import Data.List (sort, group)

splitEvery :: Int -> [a] -> [[a]]
splitEvery _ [] = []
splitEvery n xs = as : splitEvery n bs 
     where (as,bs) = splitAt n xs

solve :: [Int] -> [(Int, Int, Bool)]
solve [] = []
solve (_:rest) = 
    do {
        [u,v,w] <- splitEvery 3 rest;
        [(u, v, 0 == (w `mod` 2)),(v, u, 0 == (w `mod` 2))]
    }

distinct :: [(Int, Bool)] -> [(Int, Bool)]
distinct = map head.group.sort

solve2 :: [(Int, Int, Bool)] -> [(Int, Bool)]
solve2 dic = 
    solve3 []
    where
        solve3 :: [(Int, Bool)] -> [(Int, Bool)]
        solve3 [] =
            solve3 [(u,True),(v,w)] 
            where 
                ((u,v,w):_) = dic

        solve3 arr 
             | div (length dic) 2 < (length arr) = arr
             | otherwise = 
                solve3 $ distinct $ arr ++ do {
                    (a,w1) <- arr;
                    (b,c,w2) <- dic;
                    if a == b 
                        then
                            [(c, (w1 == w2))]
                        else
                            []
                }
                    
main :: IO ()    
main = interact $ show.solve2.solve.map read.words
