There are
N cities. There are also
K highways and
L railways running between the cities. Each
i-th highway bidirectionally connects
pi and
qi cities, and each
i-th railway bidirectionally connects
ri and
si cities. No two highways connect the same pair of cities. Similarly, no two railroads connect the same pair of cities. We will assume that cities
A and
B are connected by a highway if city
B can be reached from city
A on some highway. Here, any city is considered to be connected to a highway. Similarly, we will also define the possibility of communication by railroads. For each city, find the number of cities connected to that city by both highways and railroads.
Input
The input data comes in the following format:
N K L
p1 q1
...
pKqK
r1 s1
...
rl sL
Restrictions:
\(2<=N<=2\cdot10^5 \\ 1<=K,L<=10^5 \\ 1<=p_i,q_i,r_i,s_i<= N\\ p_i <q_i \\ r_i<s_i \\ When\ i \neq j, (p_i,q_i)\neq(p_j,q_j) \\ ?When\ i \neq j, (r_i,s_i)\neq (r_j,s_j)\)
Imprint
Print
N integers on one line, separating each number with one space. Each
i number must represent the number of cities connected to the
ith city by both highways and railroads.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
4 3 1
1 2
23
34
2 3
| 1 2 2 1 |
All four cities are connected by roads.
Only the second and third cities are connected by rail. Thus, the answers for cities are 1,2,2 and 1 respectively. |
| 2 |
4 2 2
1 2
23
14
2 3
| 1 2 2 1 |
|
| 3 |
7 4 4
1 2
23
25
67
3 5
4 5
34
6 7
| 1 1 2 1 2 2 2 |
|