| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 12 초 | 2048 MB | 8 | 6 | 6 | 75.000% |
The Intercity Caspian Package Company (ICPC) is starting a delivery service which will deliver packages between various cities near the Caspian Sea. The company plans to hire couriers to carry packages between these cities.
Each courier has a home city and a destination city, and all couriers have exactly the same travel schedule: They leave their home city at 9:00, arrive at their destination city at 12:00, leave their destination city at 14:00 and return to their home city at 17:00. While couriers are in their home or destination cities, they can receive packages from and/or deliver packages to customers. They can also hand off to or receive packages from other couriers who are in that city at the same time. Since ICPC is a personal service, packages are never left in warehouses or other facilities to be picked up later – unless the package has reached its destination, couriers have to either keep the package with themselves (during the day or during the night), or hand it off to another courier.
The company will direct the couriers to hand off packages in such a way that any package can always be delivered to its destination. Or so it is hoped! We’ll say that two cities $u$ and $v$ are connected if it is possible to deliver a package from city $u$ to city $v$ as well as from $v$ to $u$. To estimate the efficiency of their hiring process, the company would like to find, after each courier is hired, the number of pairs of cities $(u, v)$ that are connected (1ドル ≤ u < v ≤ n$).
The first line of input contains two integers $n$ and $m,ドル where $n$ (2ドル ≤ n ≤ 2 \cdot 10^5$) is the number of cities, and $m$ (1ドル ≤ m ≤ 4 \cdot 10^5$) is the number of couriers that will be hired. Couriers are numbered 1ドル$ to $m,ドル in the order they are hired. This is followed by $m$ lines, the $i$th of which contains two distinct integers $a_i$ and b$_i$ (1ドル ≤ a_i , b_i ≤ n$), denoting the home and destination cities, respectively, for courier $i$.
Output $m$ integers, denoting the number of pairs of connected cities after hiring the first 1,ドル 2, \dots , m$ couriers.
4 4 1 2 2 3 4 3 4 2
1 2 4 6