問題文

N 枚のカードがあり、順番に 1, 2, \cdots ,N 番目のカードと呼ぶ。全てのカードは表と裏にそれぞれ 0 と 1 が書かれている。

これらのカードを M 個の条件を全て満たすように、表と裏のどちらかを上にして机に置く。i 番目の条件は以下の少なくとも一方を満たすことである。

• A_i 番目のカードの上面に X_i が書かれている。
• B_i 番目のカードの上面に Y_i が書かれている。

条件を満たすようなカードの置き方が存在するような入力しか与えられないことが保証される。ただし、カードの置き方は複数あるかもしれない。以下の条件を満たす整数組 (p, q, r, s) の個数を求めよ。

• 1 \leq p, q \leq N
• \{r, s\} \subset \{0, 1\}
• 全てのカードの置き方について、以下の少なくとも一方を満たす。
  • p 番目のカードの上面に r が書かれている。
  • q 番目のカードの上面に s が書かれている。

制約

• 1 \leq N \leq 3 \times 10^4
• 0 \leq M \leq 3 \times 10^4
• 1 \leq A_i, B_i \leq N
• \{ X_i, Y_i \} \subset \{0, 1\}
• 条件を満たすようなカードの置き方が最低 1 通り存在する。
• 入力は全て整数

入力例 1

2 1
1 2 0 0

出力例 1

6

1 番目のカードと 2 番目のカードのいずれかの上面に 0 が書かれている必要があります。これを満たすように置くと、カードの表面に書かれた文字としてあり得るのは (0, 0), (1, 0), (0, 1) の 3 通りです。よって、 (p, q, r, s) としてあり得るのは、 (1, 1, 0, 1), (1, 1, 1, 0), (1, 2, 0, 0), (2, 1, 0, 0), (2, 2, 0, 1), (2, 2, 1, 0) です。

入力例 2

10 20
4 10 1 1
7 3 0 1
6 4 1 1
8 1 1 1
7 5 0 0
2 8 0 0
1 6 1 1
2 2 1 0
4 8 0 0
3 3 1 1
9 6 0 1
9 2 0 1
5 2 1 0
5 7 1 1
2 2 1 1
5 6 1 0
2 10 1 1
5 2 1 1
7 7 1 0
10 5 1 0

出力例 2

241