import Control.Arrow
import Data.List
import qualified Data.ByteString.Char8 as B
import Control.Monad
import qualified Data.IntMap as IM

main :: IO ()
main = breads >>= main'
    where
        main' nm = breads >>= main'' nm
        main'' [n, m] ps = replicateM m breads >>= print . solve n m ps

solve :: Int -> Int -> [Int] -> [[Int]] -> Int
solve n m ps xys = fst . foldl' ff (0, uft) $ zip [0..] ps
    where
        uft = foldl' (\acc [x, y] -> unionNodes (x - 1) (y - 1) acc) (makeTree n) xys
        ff (acc, t) (i, p)
            | b = (acc + 1, s)
            | otherwise = (acc, s)
            where
                (b, s) = isSame i (p - 1) t

newtype UFTree = UFTree (IM.IntMap (Int, Int))
    deriving (Show, Eq)
    
makeTree :: Int -> UFTree
makeTree n = UFTree . IM.fromList . zip [0..n] $ zip (repeat 0) [0..]

findRoot :: Int -> UFTree -> (Int, UFTree)
findRoot v t@(UFTree vs)
    | v == root = (v, t)
    | otherwise = (vr, UFTree u)
    where
        (rank, root) = vs IM.! v 
        (vr, UFTree s) = findRoot root t
        u = IM.update (return . second (const vr)) v s
        
unionNodes :: Int -> Int -> UFTree -> UFTree
unionNodes a b t 
    | c == d = t
    | ra < rb = UFTree $ IM.update (return . second (const d)) c vs
    | ra > rb = UFTree $ IM.update (return . second (const c)) d vs
    | otherwise = UFTree $ IM.update (\(x, _) -> return (x + 1, c)) d vs
    where
        (c, s) = findRoot a t
        (d, UFTree vs) = findRoot b s
        ra = fst $ vs IM.! c
        rb = fst $ vs IM.! d
        
isSame :: Int -> Int -> UFTree -> (Bool, UFTree)
isSame a b t = (c == d, u)
    where
        (c, s) = findRoot a t
        (d, u) = findRoot b s
        

breads :: IO [Int]
breads = unfoldr (\s -> second (maybe B.empty snd . B.uncons) <$> B.readInt s) <$> B.getLine