Есть
N городов. Есть также шоссе
K и железные дороги
L, проходящие между городами. Каждое
i-я шоссе двунаправленно соединяет
рi и
qi города, а каждая
i-я железная дорога двунаправленно соединяет
ri и
si города. Нет двух шоссе, соединяющих одну и ту же пару городов. Точно так же, никакие две железные дороги не соединяют одну и ту же пару городов. Будем считать, что города
A и
B соединены шоссе, если до города
B можно добраться из города
A по некоторому количеству шоссе. Здесь любой город считается соединенным с собой шоссе. Аналогичным образом, мы также определим возможность сообщения железными дорогами. Для каждого города найдите количество городов, соединенных с этим городом как шоссе, так и железными дорогами.
Входные данные
Входные данные поступают в следующем формате:
N K L
p1 q1
...
pK qK
r1 s1
...
rl sL
Ограничения:
\(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 \\ Когда\ i \neq j, (p_i,q_i)\neq(p_j,q_j) \\ ?Когда\ i \neq j, (r_i,s_i)\neq(r_j,s_j)\)
Выходные данные
Выведите
N целых чисел в одной строке, разделяя каждое число одним пробелом. Каждое
i число должно обозначать количество городов, соединенных с
i-м городом как шоссе, так и железными дорогами.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
4 3 1
1 2
2 3
3 4
2 3 |
1 2 2 1 |
Все четыре города связаны между собой дорогами.
Железной дорогой соединены только второй и третий города. Таким образом, ответы для городов 1,2,2 и 1 соответственно. |
| 2 |
4 2 2
1 2
2 3
1 4
2 3 |
1 2 2 1 |
|
| 3 |
7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7 |
1 1 2 1 2 2 2 |
|