黃鼠狼在準備給雞拜年,因此去翻了一下雞的家庭樹。雞的家庭樹很特別,因為某些原因只會記錄家庭中的女性成員。
雞群總共有 $N$ 隻母雞,編號為 $1\sim N$。家庭樹上面的 $N$ 個節點分別代表各隻雞,此外還有 $N-1$ 條邊,對於每條邊的兩端 $u_i,v_i$,表示 $u_i,v_i$ 是母女關係,但是不知道誰的輩分比較大。
順帶一提,因為家族詛咒的關係(與樹的定義),這群雞的家庭樹不會有環。
為了省錢,黃鼠狼只想要送紅包給雞的老祖宗。但是,他發現家庭樹的紙張沒有寫說所有人的祖先是誰,因此他沒辦法判斷這一群美味可口的食材的老祖宗是誰。
他只記得 $Q$ 個資訊:每個資訊為兩個整數 $a_i,b_i$,表示 $a_i$ 是 $b_i$ 的祖先。
於是,黃鼠狼決定送紅包給所有可能是老祖宗的母雞們。他想要知道他這樣會需要準備幾包紅包,分別是送給哪些雞。
祖先的定義:首先,老祖宗是所有人的祖先。接下來,一隻雞的母親、外祖母、外曾祖母等都是她的祖先。準確來說,一隻雞到老祖宗最短路徑上的所有節點(包含自己)都是自己的祖先。(其實就是有根樹祖先的定義)
請將符合的雞按照編號由小到大輸出,保證至少有一隻雞符合所有限制。
請注意,因為黃鼠狼老了,所以可能會一直講同樣的資訊很多次。
第一行輸入一個正整數 $N$。
接下來輸入 $N-1$ 行,每行輸入兩正整數 $u_i,v_i$,表示家庭樹上的邊。
接來輸入一個整數 $Q$,表示黃鼠狼所知道的關係數量。
接下來輸入 $Q$ 行,每行輸入兩正整數 $a_i,b_i$,表示 $a_i$ 為 $b_i$ 的祖先。
對於所有測試資料:
第一行輸出一個整數 $K$ ,表示總共有幾隻雞可能是老祖宗。
第二行輸出 $K$ 個整數,代表可能是老祖宗的雞的編號,由數字小到大輸出,以空白分隔。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0 | 範例測資 | 0 |
2 | 0~10 | $N,Q \leq 500$ | 19 |
3 | 0~20, 71 | $N,Q\leq 3000$ | 20 |
4 | 4, 12, 20~30, 37~38, 46, 54, 61~62, 70, 73~75 | $|u_i-v_i|=1$ | 11 |
5 | 0, 31~50, 71~72 | $a_i,b_i$ 是一條邊的兩端 | 27 |
6 | 0~78 | 無其他限制 | 23 |