Sammy and Meera liked adventures a lot. Once in a while they used to set out adventures. This time to carry out their adventure, Sammy decided to choose two cities from a map and help all the poor people on their way starting from one of them to the other. But to choose the starting and ending location, Sammy needed to know the number of ways to choose two of such locations from the map. As he remains busy solving critical problems about the Life, the Universe, and Everything, he decided to let other people solve these smaller problems.
Right in the locality where they used to study, lived a small boy named Golu. Sammy decided to put Golu to work out some smaller tasks. Golu being a humble boy, always wanted to help Sammy. He managed to solve the problem, but he is confused as to whether the result is correct or not. As Golu doesn’t want to let Sammy down, he asked for your help to verify the result.
Golu will provide you information about how the cities are connected. The map contains N roads, each connecting two separate cities. For each of the roads he gives you sequentially, he expects you to answer the result with the information currently available at hand. You can safely assume that no city is connected to itself.
Line - 1: Number of roads N (1 <= N <= 1000000).
Line - 2 … N+1: Two integers u and v (1 <= u,v <= 1000000) meaning that there will be a road connecting u and v.
For each road, output one integer in a line, that is, the apparent result from the information given up to that point.
| Input | Output |
|---|---|
2 1 2 2 3 | 1 3 |
For the first road, we only have information about 2 cities 1 and 2. We only have 1 way of choosing the start and destination city pair (1, 2).
For the second road, the resultant pairs can be (1, 2), (1, 3), (2, 3).