\((A_i,B_i)\) から重複を取り除いておきます．

このとき， \((x,y)\) が条件を満たす条件は，以下のように記述できます．

• \((A_i,B_i)=(x,y)\) なる \(i\) が存在するとき
  • \((A_j,B_j)\) と \((x,y)\) の共通要素は， \(j=i\) のとき \(2\) つ， \(j\ne i\) のとき高々 \(1\) つなので，その場合に常に \(1\) つであればよい．これは \(x,y\) の次数の和が \(M+1\) であることと同値．
• \((A_i,B_i)=(x,y)\) なる \(i\) が存在しないとき
  • \((A_j,B_j)\) と \((x,y)\) の共通要素は高々 \(1\) つなので，全ての \(j\) に対して \(1\) つであればよい．これは \(x,y\) の次数の和が \(M\) であることと同値．

この個数は以下のように求められます．

• まず，全ての場合で下の条件を適用させる．これは，各 \(i(0\le i\le M)\) について次数 \(i\) の頂点の個数を前計算したのち， \(x,y\) の次数を全探索することで \(O(N+M)\) で計算できる．
• \(i\) を全探索し， \((x,y)=(A_i,B_i)\) の場合を考える．上の条件が成り立つなら答に加算し，下の条件が成り立ち余分に足されているなら答から減算する．

これより \(O(N+M)\) で計算できます．重複を取り除くところに std::set を利用するとさらに \(O(M\log M)\) かかりますが十分高速です．