TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

76.7% (23/30)

Submission's AC Ratio

23.7% (44/186)

Tags

Description

黃鼠狼在準備給雞拜年,因此去翻了一下雞的家庭樹。雞的家庭樹很特別,因為某些原因只會記錄家庭中的女性成員。
雞群總共有 $N$ 隻母雞,編號為 $1\sim N$。家庭樹上面的 $N$ 個節點分別代表各隻雞,此外還有 $N-1$ 條邊,對於每條邊的兩端 $u_i,v_i$,表示 $u_i,v_i$ 是母女關係,但是不知道誰的輩分比較大。
順帶一提,因為家族詛咒的關係(與樹的定義),這群雞的家庭樹不會有環。

為了省錢,黃鼠狼只想要送紅包給雞的老祖宗。但是,他發現家庭樹的紙張沒有寫說所有人的祖先是誰,因此他沒辦法判斷這一群美味可口的食材的老祖宗是誰。
他只記得 $Q$ 個資訊:每個資訊為兩個整數 $a_i,b_i$,表示 $a_i$ 是 $b_i$ 的祖先。
於是,黃鼠狼決定送紅包給所有可能是老祖宗的母雞們。他想要知道他這樣會需要準備幾包紅包,分別是送給哪些雞。

祖先的定義:首先,老祖宗是所有人的祖先。接下來,一隻雞的母親、外祖母、外曾祖母等都是她的祖先。準確來說,一隻雞到老祖宗最短路徑上的所有節點(包含自己)都是自己的祖先。(其實就是有根樹祖先的定義)

請將符合的雞按照編號由小到大輸出,保證至少有一隻雞符合所有限制。
請注意,因為黃鼠狼老了,所以可能會一直講同樣的資訊很多次。

Input Format

第一行輸入一個正整數 $N$。
接下來輸入 $N-1$ 行,每行輸入兩正整數 $u_i,v_i$,表示家庭樹上的邊。
接來輸入一個整數 $Q$,表示黃鼠狼所知道的關係數量。
接下來輸入 $Q$ 行,每行輸入兩正整數 $a_i,b_i$,表示 $a_i$ 為 $b_i$ 的祖先。

對於所有測試資料:

  • $2 \le N \le 2 \times 10 ^ 5$
  • $0 \le Q \le 2 \times 10 ^ 5$
  • $1 \le u_i,v_i,a_i,b_i \le N$
  • $a_i\neq b_i$
  • 保證輸入進來的 $N-1$ 條邊會形成一棵樹

Output Format

第一行輸出一個整數 $K$ ,表示總共有幾隻雞可能是老祖宗。
第二行輸出 $K$ 個整數,代表可能是老祖宗的雞的編號,由數字小到大輸出,以空白分隔。

Sample Input 1

5
1 2
2 3
3 4
3 5
2
2 1
4 3

Sample Output 1

1
4

Hints

Problem Source

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3 5 6
1 1000 524288 65536 2 3 6
2 1000 524288 65536 2 3 6
3 1000 524288 65536 2 3 6
4 1000 524288 65536 2 3 4 6
5 1000 524288 65536 2 3 6
6 1000 524288 65536 2 3 6
7 1000 524288 65536 2 3 6
8 1000 524288 65536 2 3 6
9 1000 524288 65536 2 3 6
10 1000 524288 65536 2 3 6
11 1000 524288 65536 3 6
12 1000 524288 65536 3 4 6
13 1000 524288 65536 3 6
14 1000 524288 65536 3 6
15 1000 524288 65536 3 6
16 1000 524288 65536 3 6
17 1000 524288 65536 3 6
18 1000 524288 65536 3 6
19 1000 524288 65536 3 6
20 1000 524288 65536 3 4 6
21 1000 524288 65536 4 6
22 1000 524288 65536 4 6
23 1000 524288 65536 4 6
24 1000 524288 65536 4 6
25 1000 524288 65536 4 6
26 1000 524288 65536 4 6
27 1000 524288 65536 4 6
28 1000 524288 65536 4 6
29 1000 524288 65536 4 6
30 1000 524288 65536 4 6
31 1000 524288 65536 5 6
32 1000 524288 65536 5 6
33 1000 524288 65536 5 6
34 1000 524288 65536 5 6
35 1000 524288 65536 5 6
36 1000 524288 65536 5 6
37 1000 524288 65536 4 5 6
38 1000 524288 65536 4 5 6
39 1000 524288 65536 5 6
40 1000 524288 65536 5 6
41 1000 524288 65536 5 6
42 1000 524288 65536 5 6
43 1000 524288 65536 5 6
44 1000 524288 65536 5 6
45 1000 524288 65536 5 6
46 1000 524288 65536 4 5 6
47 1000 524288 65536 5 6
48 1000 524288 65536 5 6
49 1000 524288 65536 5 6
50 1000 524288 65536 5 6
51 1000 524288 65536 6
52 1000 524288 65536 6
53 1000 524288 65536 6
54 1000 524288 65536 4 6
55 1000 524288 65536 6
56 1000 524288 65536 6
57 1000 524288 65536 6
58 1000 524288 65536 6
59 1000 524288 65536 6
60 1000 524288 65536 6
61 1000 524288 65536 4 6
62 1000 524288 65536 4 6
63 1000 524288 65536 6
64 1000 524288 65536 6
65 1000 524288 65536 6
66 1000 524288 65536 6
67 1000 524288 65536 6
68 1000 524288 65536 6
69 1000 524288 65536 6
70 1000 524288 65536 4 6
71 1000 524288 65536 3 5 6
72 1000 524288 65536 5 6
73 1000 524288 65536 4 6
74 1000 524288 65536 4 6
75 1000 524288 65536 4 6
76 1000 524288 65536 6
77 1000 524288 65536 6
78 1000 524288 65536 6