import Control.Applicative
import Control.Monad
import Data.Array.IO
import Data.List
import qualified Data.ByteString.Char8 as BS
import Data.Maybe
import Data.Bits

listToTuple3 [a,b,c] = (a,b,c)

thrd (_,_,x) = x
tuple3To2 (x,y,_) = (x,y)

unite (x:[]) = [x]
unite ((a,b):xs) = if b==c then (a,d):ys else (a,b):(c,d):ys
  where ((c,d):ys) = unite xs

modifyArray arr i f = readArray arr i >>= \x -> writeArray arr i (f x)

main = do
  (n:c:_) <- map read . words <$> getLine :: IO [Int]

  arr <- newArray (0,100000) 0 :: IO (IOArray Int Int)

  dat <- map (unite . sort . map tuple3To2) . groupBy (\x y -> thrd x == thrd y) . map (listToTuple3 . map (fst . fromJust . BS.readInt) . BS.words) . BS.lines <$> BS.getContents :: IO [[(Int,Int)]]
    
  forM_ (zip [0..] dat) $ \(i,xs) -> do
    forM_ xs $ \(s,t) -> do
      modifyArray arr (s-1) (\x -> x + (bit i :: Int))
      modifyArray arr t (\x -> x - (bit i :: Int))

  (l,r) <- getBounds arr
  forM_ [l+1..r] $ \i -> do
    readArray arr (i-1) >>= \x -> modifyArray arr i (+x)

  print =<< maximum . map popCount <$> getElems arr
