import Data.Maybe
import Data.List as List
import Data.Map.Strict as Map
import Data.Char
import qualified Data.ByteString.Char8 as BS

main :: IO()
main = do
  _ <- BS.getLine
  es <- parseInput <$> BS.getContents
  let coloredEdges = paint es
  let nc = numColors coloredEdges
  print nc
  mapM_ print $ lookupEdgeColors coloredEdges es
  where
    parseInput = List.map ((\[x, y] -> (x, y)) . parseLine) . BS.lines
    parseLine = unfoldr (BS.readInt . BS.dropWhile isSpace)
    lookupEdgeColors ce = List.map (lookupColor ce)
    lookupColor ce (x,y) = fromJust $ Map.lookup y $ fromJust $ (Map.lookup x ce)

numColors :: Map Int (Map Int Int) -> Int
numColors = maximum . Map.map (Map.foldr max 0)

paint :: [(Int, Int)] -> Map Int (Map Int Int)
paint edges  = Map.fromList $ paintTree edgesMap 0 1
  where
    edgesMap = Map.fromList . List.map toKeyValue . aggregate $ edges
    aggregate = groupBy (\x y -> fst x == fst y) . sortOn fst
    toKeyValue = (,) <$> fst.head <*> sort.(List.map snd)

paintTree :: Map Int [Int] -> Int -> Int -> [(Int, (Map Int Int))]
paintTree esMap pColor cNum = case Map.lookup cNum esMap of
  Just childNodes -> (cNum, edgesTo childNodes):List.concatMap traverseNodes (nodeColorPair childNodes)
  Nothing -> []
  where
    nodeColorPair nodes = zip nodes (List.filter (/=pColor) [1..])
    edgesTo = Map.fromList . nodeColorPair
    traverseNodes (node, color) = paintTree esMap color node