import Control.Arrow
import Data.List
import qualified Data.ByteString.Char8 as B
import Control.Monad
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM

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 acc (x - 1) $ y - 1) (makeTree n) xys
        ff (acc, t) (i, p)
            | b = (acc + 1, s)
            | otherwise = (acc, s)
            where
                (b, s) = isSame t i $ p - 1

newtype UFTree = UFTree (V.Vector (Int, Int))
    deriving (Show, Eq)
    
makeTree :: Int -> UFTree
makeTree n = UFTree . V.fromListN n $ zip (repeat 0) [0..]

findRoot :: UFTree -> Int -> (Int, UFTree)
findRoot t@(UFTree vs) v
    | v == root = (v, t)
    | otherwise = (vr, UFTree u)
    where
        (rank, root) = vs V.! v 
        (vr, UFTree s) = findRoot t root
        u = V.modify (\xs -> VM.modify xs (second (const vr)) v) s 
        
unionNodes :: UFTree -> Int -> Int -> UFTree
unionNodes t a b 
    | c == d = t
    | ra < rb = UFTree $ V.modify (\xs -> VM.modify xs (second (const d)) c) vs
    | ra > rb = UFTree $ V.modify (\xs -> VM.modify xs (second (const c)) d) vs
    | otherwise = UFTree $ V.modify (\xs -> VM.modify xs (first succ . second (const c)) d) vs
    where
        (c, s) = findRoot t a
        (d, UFTree vs) = findRoot s b
        ra = fst $ vs V.! c
        rb = fst $ vs V.! d
        
isSame :: UFTree -> Int -> Int -> (Bool, UFTree)
isSame t a b = (c == d, u)
    where
        (c, s) = findRoot t a
        (d, u) = findRoot s b
        

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