芽芽最喜歡送別人禮物了,無論是聖誕節、資訊之芽創立週年紀念日、或是伸展樹論文發表紀念日,各式各樣的節日都會送人禮物。
為了讓收到的人有拆禮物的快樂,芽芽會把禮物包在禮物裡面,這樣就可以讓收到的人拆很久。
現在他的房間裡有大量的禮物箱,他想要把一些禮物箱包到其他禮物箱內。
每次芽芽會挑選一個箱子 $y$,把這個箱子以及裡面的所有內容物都包到箱子 $x$ 裡面。
也就是說,如果箱子 $y$ 內已經有其他箱子的話,那麼這些箱子也會連著箱子一起(間接的)被放入箱子 $x$ 內。
最後所有最外層的箱子會被包裝成一個禮物。
你不用擔心芽芽會不會包不下去,既然禮物都包出來了,內容物鐵定是沒有違反物理原則的。
目前芽芽已經做完一系列的操作了,現在他想知道某個禮物裡面的箱子總數。
不過禮物的包裝紙都用緞帶包好了,粗心的芽芽只記得他是怎麼包裝這些箱子的,你能透過這些資訊幫他解決這個問題嗎?
輸入檔第一行有一個數字 $T\,(T \leq 100)$ 代表測試資料的筆數。
在一筆測試資料當中,第一行包含兩個以空白間隔的整數 $n$ 和 $m$($1\leq n \leq 10 ^ 5, T \times n \leq 10 ^ 6 , 0 \leq m \leq n-1$),
代表一開始芽芽有 $n$ 個沒有裝著任何東西的箱子,編號從 $1$ 到 $n$,而芽芽包裝的過程是 $m$ 次操作。
接下來有 $m$ 行,每行包含兩個以空白間隔的整數 $x$ 和 $y$,代表芽芽將整個箱子 $y$ 放入箱子 $x$ 中。
再接下來的一行包含一個整數 $q\,(1 \leq q \leq n)$,代表接下來有 $q$ 筆詢問。
最後的 $q$ 行每行包含一個整數 $x$,代表芽芽想知道最外層是 $x$ 號箱子的禮物中總共有多少箱子(同時包含箱子 $x$)。
保證輸入的操作皆合法,箱子一旦被包入其他箱子中,就不會再直接被包到另外的箱子裡。
也就是說輸入的 $m$ 行中 $y$ 都相異。
對於每個詢問,輸出一行包含一個整數,最外層是 $x$ 號箱子的禮物中總共有多少箱子(同時包含箱子 $x$)。
圖二:範例輸入操作後的箱子情況。
NEOJ Problem 49
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 3~12 | $n\leq 100$ | 10 |
2 | 0~2 | 90 |