Codeforces Round 109 (Div. 1) |
---|
Закончено |
Вам предложили работу в компании, разрабатывающей крупную социальную сеть. Ваше первое задание связано с поиском профилей, с большой вероятностью принадлежащих одному и тому же пользователю.
В социальной сети зарегистрировано 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) считается одинаковыми.
В первой строке записано два целых числа n и m (1 ≤ n ≤ 106, 0 ≤ m ≤ 106), разделенных пробелом — количество профилей и количество пар друзей соответственно.
В следующих m строках записаны описания пар друзей в формате «v u», где v и u (1 ≤ v, u ≤ n, v ≠ u) — номера профилей, являющихся друзьями. Гарантируется, что каждая неупорядоченная пара друзей встречается не более одного раза и никакой профиль не является другом самого себя.
Выведите единственное целое число — количество неупорядоченных пар профилей, являющихся двойниками.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать спецификатор %I64d.
3 3
1 2
2 3
1 3
3
3 0
3
4 1
1 3
2
В первом и втором примерах любые два профиля являются двойниками.
В третьем примере двойниками являются пары профилей (1, 3) и (2, 4).
Название |
---|