D2 - Dual Friendship [Hard]

問題 D1 とは制約と内容が異なります

新たに，「人 と人 とが人 を介して友達の友達である」とは 整数 が下記の条件を満たすことを指します．

• 人 と人 とが互いに友達である
• 人 と人 とが互いに友達である

下記の条件をすべて満たす正整数の組 は何通りあるか，求めてください．

• 人 と人 とが人 を介して友達の友達である

• ならば
• 入力はすべて整数である

入力は D1 と同一のものです．

4 3
1 2
2 3
2 4

3

のときに条件を満たします．

4 4
1 2
2 3
2 4
1 3

5

のときに条件を満たします．

4 5
1 2
2 3
2 4
1 3
3 4

8

のときに条件を満たします．