A coastal traffic-control authority has deployed n signal beacons along a shipping lane. Each beacon continuously broadcasts on two channels, transmitting one frequency value on channel one and another on channel two (a beacon may even transmit the same value on both channels). Two beacons are called a twin pair if the pair of frequencies they broadcast matches exactly, regardless of which channel carried which value — that is, {channel-one value, channel-two value} is the same unordered pair for both beacons. Count how many twin pairs exist among all n beacons.
The first line contains a single integer n, the number of beacons. Each of the next n lines contains two integers a and b — the frequencies broadcast by that beacon on channel one and channel two, respectively.
Print a single integer: the number of index pairs (i, j) with i < j such that beacon i and beacon j form a twin pair.
Example 1
Input
6 1 2 2 1 3 4 5 6 6 5 3 4
Expected
3
Explanation
Beacons 1 and 2 broadcast {1,2} with the channels swapped, so they form a twin pair. Beacons 3 and 6 both broadcast {3,4}, another twin pair. Beacons 4 and 5 broadcast {5,6} and {6,5}, a third twin pair. No other beacon shares a frequency set with another, so the total is 3.
Example 2
Input
5 1 2 1 2 1 1 1 2 2 2
Expected
3
Explanation
Three beacons (the 1st, 2nd, and 4th) all broadcast {1,2}, contributing C(3,2) = 3 twin pairs among themselves. The beacon broadcasting {1,1} and the beacon broadcasting {2,2} each appear only once, so neither contributes any pair. The total is 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →