Вам предложили работу в компании, разрабатывающей крупную социальную сеть. Ваше первое задание связано с поиском профилей, с большой вероятностью принадлежащих одному и тому же пользователю.
В социальной сети зарегистрировано n профилей, пронумерованных от 1 до n. Некоторые пары среди них являются друзьями (отношение «быть друзьями» взаимно, то есть если i является другом j, то и j является другом i). Будем говорить, что профили i и j (i ≠ j) являются двойниками, если для любого профиля k (k ≠ i, k ≠ j), верно одно из двух утверждений: либо k дружит и с i, и с j, либо k не дружит ни с одним из них. При этом i и j могут как дружить между собой, так и не дружить.
Вам нужно посчитать количество различных неупорядоченных пар (i, j), таких что профили i и j — двойники. Обратите внимание, что пары неупорядоченные, то есть пары (a, b) и (b, a) считается одинаковыми.
Выходные данные
Выведите единственное целое число — количество неупорядоченных пар профилей, являющихся двойниками.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать спецификатор %I64d.
Примечание
В первом и втором примерах любые два профиля являются двойниками.
В третьем примере двойниками являются пары профилей (1, 3) и (2, 4).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2
2 3
1 3
|
3
|
|
2
|
3 0
|
3
|
|
3
|
4 1
1 3
|
2
|