#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Title

### Problem Statement

There are `N` cities. There are also `K` roads and `L` railways, extending between the cities.
The `i`-th road bidirectionally connects the `p _{i}`-th and

`q`-th cities, and the

_{i}`i`-th railway bidirectionally connects the

`r`-th and

_{i}`s`-th cities. No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.

_{i}We will say city `A` and `B` are *connected by roads* if city `B` is reachable from city `A` by traversing some number of roads. Here, any city is considered to be connected to itself by roads.
We will also define *connectivity by railways* similarly.

For each city, find the number of the cities connected to that city by both roads and railways.

### Constraints

`2 ≦ N ≦ 2*10`^{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 ≠ j`,`(p`_{i}, q_{i}) ≠ (p_{j}, q_{j}) - When
`i ≠ j`,`(r`_{i}, s_{i}) ≠ (r_{j}, s_{j})

### Input

The input is given from Standard Input in the following format:

NKLp_{1}q:_{1}p_{K}q_{K}r_{1}s:_{1}r_{L}s_{L}

### Output

Print `N` integers. The `i`-th of them should represent the number of the cities connected to the `i`-th city by both roads and railways.

### Sample Input 1

4 3 1 1 2 2 3 3 4 2 3

### Sample Output 1

1 2 2 1

All the four cities are connected to each other by roads.

By railways, only the second and third cities are connected. Thus, the answers for the cities are `1, 2, 2` and `1`, respectively.

### Sample Input 2

4 2 2 1 2 2 3 1 4 2 3

### Sample Output 2

1 2 2 1

### Sample Input 3

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

### Sample Output 3

1 1 2 1 2 2 2

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 15 | 1s | 256MB | Minimum |

2 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o connectivity -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512