TopCoder

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

40.0% (2/5)

Tags

Description

現充國由 N 個島嶼組成,其中有 N1 條連接兩個島嶼的雙向橋梁,且任兩個島嶼可以經過若干個橋梁互相抵達。

為了節省通勤時間,現充國的總統 arctan 做了以下決策:

對於兩個島嶼 A,B,如果 AB 的路徑需要經過 K 個橋樑,且不存在另外兩個島嶼 C,D ,使得 CD 的路徑需要經過至少 K+1 個橋樑,則在 AB 經過的每個島嶼都建設一個高鐵站,並開通一條往返 AB 的高鐵路線。

請身為現充國總理的你,幫 arctan 總統檢查哪些島嶼需要建設高鐵站。

Input Format

輸入包含多筆測資,第一行輸入包含一個正整數 T(1T105),代表測資數量。

每筆測資中,

第一行為一個正整數 N(2N5×105) 代表現充國的島嶼數量,每個島嶼以 1N 的編號代表。

接著的 N1 行,每行有兩個以一個空白隔開的整數 uv (1u,vN),代表編號為 uv 島嶼之間有橋梁連接。保證任兩個島嶼可以經由若干個橋梁互相抵達。

其中每筆測資中 N 的總和至多為 105

Output Format

每筆測資輸出一行,其中包含 N 數字,如果第 i 個島嶼需要建設高鐵站則在第 i 個數字輸出 1,否則在第 i 個數字輸出 0

Sample Input 1

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

Sample Output 1

1 1 1
1 1 1 1
1 1 1 1 1 0

Hints

Problem Source

APCS 歷屆

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 1~15 每筆測資 N 的總和至多為 100 10
3 0~40 每筆測資 N 的總和至多為 3000 30
4 0~80 無額外限制 60

Testdata and Limits

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