Along a fog-prone coastline, lighthouses fire numbered beacon flashes, and passing ships radio back short acknowledgment records naming the flash they are answering. A relay operator's logbook mixes both kinds of entries together, and because of radio retransmissions the very same acknowledgment sometimes gets logged twice. Given the full logbook, report how many distinct acknowledgments each beacon flash received.

Input format

• Line 1: a single integer n, the number of logbook entries.
• Each of the next n lines contains two integers id parent separated by a space, describing one logbook entry.
  • If parent is -1, the entry records a beacon flash, and id is that flash's identifier.
  • Otherwise, the entry records an acknowledgment of the beacon flash whose identifier equals parent, and id is the acknowledgment's own identifier. Every acknowledgment refers directly to a beacon flash — never to another acknowledgment.
  • The same id may appear on more than one line (an accidental retransmission); every line carrying a given id describes the exact same logbook entry and must be counted only once.

Output format

Print one line per distinct beacon flash, in ascending order of its identifier, as two integers separated by a space: the flash's identifier followed by the number of distinct acknowledgments it received (0 if none).

Constraints

• 1 <= n <= 200000
• 1 <= id <= 10^9 for every entry
• parent is either -1 or an id that appears somewhere in the log as a beacon flash (i.e. with parent = -1)
• At least one line has parent = -1 (there is always at least one beacon flash).

5
101 -1
201 101
202 101
201 101
303 -1

101 2
303 0

6
10 -1
50 -1
11 10
12 10
51 50
11 10

10 2
50 1