Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:128 MB

#294. 三分图二元环计数

统计

题目描述

给定一个有向三分图,求其二元环个数。

输入格式

输入第一行包含 4 个正整数 $n_1,n_2,n_3,m$,表示图的三部分的点数和图的边数。

接下来 $m$ 行每行两个正整数 $x,y\ (1\le x,y\le n_1+n_2+n_3)$,表示一条 $x\to y$ 的边。

设 $f(x)=\begin{cases}0,x\in [1,n_1]\\ 1,x\in [n_1+1,n_1+n_2]\\2, x\in [n_1+n_2+1,n_1+n_2+n_3]\end{cases}$。保证 $f(x)\ne f(y)$。

输出格式

输出三分图的二元环个数。

数据范围

$1\le n_1,n_2,n_3\le 10^8$,$0\le m\le 2\times 10^5$