A long-haul trucking cooperative runs supply convoys along a shared highway corridor. To save fuel, trucks travel in tight two-vehicle formations: one truck out front acts as the "lead," breaking the wind, while a second truck tails closely behind as the "wingman," drafting in the lead's slipstream. Drivers rotate constantly — the same truck might lead one leg of the journey and draft as a wingman on another leg entirely. The dispatch log records every completed leg as a pair of truck IDs: the lead and its wingman for that leg.

For every truck ID that has led at least one leg of the convoy (i.e. appeared as a lead in the log at least once), report how many total legs across the entire log that same truck ID spent drafting as the wingman behind some lead (its own legs as a wingman behind any lead, counted with multiplicity — the same pair may repeat, and each occurrence counts separately). If a truck that has led never once drafted as a wingman, report a count of 0 for it. Truck IDs that never appear as a lead are not reported at all, even if they drafted many times.

Input format

Line 1: a single integer n — the number of logged convoy legs. Next n lines: two integers lead_i wingman_i — the truck ID leading and the truck ID drafting behind it on leg i. It is guaranteed lead_i != wingman_i. The same ordered pair may repeat across multiple lines.

Output format

Let D be the set of distinct truck IDs that appear as a lead at least once in the log. Print |D| lines, one per truck ID in D, in strictly increasing order of truck ID. Each line contains two integers separated by a space: the truck ID, then the total number of legs (across the whole log) in which that same truck ID appears as the wingman value.

Constraints

1 <= n <= 2*10^5 1 <= lead_i, wingman_i <= 10^9 lead_i != wingman_i for every logged leg

4
1 2
2 3
3 1
2 1

1 2
2 1
3 1

3
10 20
20 30
30 40

10 0
20 1
30 1