import Data.List
import Data.Ord
import Control.Monad
--import Debug.Trace

traceShow :: (Show a) => a -> b -> b
traceShow a = id

width::Int->Int->[[Int]]->([Int], Int)
width p v es | null next = ([v], 0)
             | otherwise = (maxvs, maxd + 1)
    where
      next = delete p $ es !! v
      nas  = map (\r -> width v r es) $ next
      maxd = maximum $ map snd $ nas
      maxvs = join $ map fst $ filter ((==maxd) . snd) $ nas

rme::Int->[Int]->[[Int]]->[Int]
rme k [] es = []
rme k (v:vs) es | k >= w          = (v:vs,nvs) `traceShow` []
                | length nvs > 1  = (v:vs,nvs) `traceShow` minimumBy (comparing length) $ map fst $ take 2 nvs
                | length nvs == 1 = (v:vs,nvs) `traceShow` fst $ head nvs
                | otherwise       = [v]
    where
      next = delete v $ es !! v
      nvs = reverse $ sortBy (comparing snd) $ map (\r -> width v r es) $ next
      w = (+1) $ sum $ map snd $ take 2 nvs

solve k vs es | null r    = ("solve1",k,vs,r) `traceShow` 0
              | otherwise = ("solve2",k,vs,r) `traceShow` (length r) + (solve k (vs \\ r) nes)
    where
      r = rme k vs es
      nes = foldr (\v es -> map (delete v) es) es r
              
toes::Int->[Int]->[[Int]]
toes n es = map sort $ toes' es def 
    where
      def = replicate (n+1) []
      toes' [] x = x
      toes' (a:b:ex) x = toes' ex $ add a b x
      add a b x = map (add' a b) $ zip [0..] x
      add' a b (i, x) | a == i    = b:x
                      | b == i    = a:x
                      | otherwise = x
                                   
run::[Int]->Int
run (n:k:esr) = solve k [1..n] es
    where
      es = toes n esr
      

f = show . run . map read . words

main = interact f