CF154C Double Profiles

You have been offered a job in a company developing a large social network. Your first task is connected with searching profiles that most probably belong to the same user. The social network contains $ n $ registered profiles, numbered from $ 1 $ to $ n $ . Some pairs there are friends (the "friendship" relationship is mutual, that is, if $ i $ is friends with $ j $ , then $ j $ is also friends with $ i $ ). Let's say that profiles $ i $ and $ j $ ( $ i≠j $ ) are doubles, if for any profile $ k $ ( $ k≠i $ , $ k≠j $ ) one of the two statements is true: either $ k $ is friends with $ i $ and $ j $ , or $ k $ isn't friends with either of them. Also, $ i $ and $ j $ can be friends or not be friends. Your task is to count the number of different unordered pairs ( $ i,j $ ), such that the profiles $ i $ and $ j $ are doubles. Note that the pairs are unordered, that is, pairs ( $ a,b $ ) and ( $ b,a $ ) are considered identical.

N/A

N/A

In the first and second sample any two profiles are doubles. In the third sample the doubles are pairs of profiles $ (1,3) $ and $ (2,4) $ .