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

numColors :: [(Int,Int)] -> Int
numColors = maximum . List.map length . group . sort . List.foldr (\(x, y) zs -> x:y:zs) []

paint :: [(Int, Int)] -> Map (Int, 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, Int), Int)]
paintTree esMap pColor cNum = case Map.lookup cNum esMap of
  Just childNodes -> paintNode esMap pColor cNum childNodes
  Nothing -> []

paintNode :: Map Int [Int] -> Int -> Int -> [Int] -> [((Int, Int), Int)]
paintNode esMap pColor currentNum childNodes =
  concatMap (\(childNum, color) -> (edgeToChild currentNum childNum color):(paintTree esMap color childNum)) nodeColorPairs
  where
    nodeColorPairs = zip childNodes (List.filter (/= pColor) [1..])
    edgeToChild p ch col = ((p, ch), col)