import Data.Bool
import Data.Char
import Data.List
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector as V
main=print.solve.map(unfoldr$B.readInt.B.dropWhile isSpace).B.lines=<<B.getContents
solve([n,k]:ab)=if odd k then r1 else r2 where
  d=k`div`2
  es=map(\[a,b]->(a-1,b-1))ab
  g=V.accum(flip(:))(V.replicate n[])$concatMap(\(a,b)->[(a,b),(b,a)])es
  r1=minimum$map(\(a,b)->f 0 a b+f 0 b a)es
  r2=minimum$map(\i->f 0 i i)[0..n-1]
  f i p v=foldr(+)(bool 0 1(i>d)).map(f(i+1)v).filter(/=p)$g V.! v