問題文

SPD君は、イベント運営の報酬として $N$ 個の行列からなる多重集合 $S$ を貰いました。

$i$ ($1 \le i \le N$) 番目の行列の形状は、 $H_i \times W_i$ です。

沢山の行列は場所を取ってしまうので、SPD君は全ての行列を掛け合わせて $1$ つの行列にしようとしています。

具体的には、 $S$ の要素が $1$ つになる、または掛け合わせることができる $2$ 要素がなくなるまで下の操作を繰り返します。

• $S$ から $X \cdot Y$ が演算可能な $2$ つの要素 $X$ , $Y$ を選ぶ。 $S$ から $X$ , $Y$ を削除し、$X \cdot Y$ を $S$ に加える。

最後に $S$ の要素が $1$ つになった時、その行列の異なる形状として考えられるものは何通りあるか求めてください。ただし、どのように操作しても $S$ の要素を $1$ つにできない場合は $0$ を出力してください。

$2$つの行列 $X$ ( 形状 $H_X \times W_X$ ) と $Y$ ( 形状 $H_Y \times W_Y$ )に関して、$ X \cdot Y $ は $ W_X = H_Y $ のとき、またその時に限り演算可能であり、その形状は $H_X \times W_Y$ になることに注意してください。

また、 $2$ つの行列の形状が異なるとは、行の数・列の数の内少なくとも片方が異なっていることを指します。

入力

$N$
$H_1\ W_1$
$H_2\ W_2$
$\vdots$
$H_N\ W_N$

• 入力は全て整数
• $2 \le N \le 2 \times 10^5$
• $1 \le H_i \le 2 \times 10^5$
• $1 \le W_i \le 2 \times 10^5$

出力

最後に改行してください。

サンプル

3
1 2
2 2
2 3

1

2
7 8
8 7

2

5
4 2
6 3
5 9
7 1
8 10

0