No.2160 Three Dominators
Problem Statement
There is an undirected graph $G$ with $N_1+N_2+N_3+2$ $(=N)$ vertices. Here, $N_1,N_2,N_3$ are non-negative integers, and their values are given. The vertices are numbered as vertex $1$ , vertex $2$ , vertex $3$ , $\ldots$. $G$ may contain multiple edges, but it contains no self-loops.
Let $s=N_1+N_2+N_3+1$ , $t=N_1+N_2+N_3+2$ . The graph $G$ contains the following $3$ paths ( main paths ), which do not share edges.
- Vertex $s$ , vertex $1$ , vertex $2$ , $\ldots$ , vertex $N_1$ , vertex $t$
- Vertex $s$ , vertex $N_1+1$ , vertex $N_1+2$ , $\ldots$ , vertex $N_1+N_2$ , vertex $t$
- Vertex $s$ , vertex $N_1+N_2+1$ , vertex $N_1+N_2+2$ , $\ldots$ , vertex $N_1+N_2+N_3$ , vertex $t$
The edges of $G$ that are not contained in the main paths are called augmenting edges. Let $M$ be the number of augmenting edges. For each augmenting edge, the numbers $U_i$ , $V_i$ ( $1\leq i \leq M$ ) of the $2$ vertices it directly connects are given.
How many sets of $3$ distinct edges $x$ , $y$ , $z$ of the graph $G$ are there such that removing the edges $x$ , $y$ , $z$ from $G$ disconnects the $2$ vertices $s$ , $t$? Sets obtained by reordering $x$ , $y$ , $z$ are regarded as the same and counted once.
Constraints
The input satisfies the following constraints.
- $0 \leq N_i$ $(i=1,2,3)$
- $N_1+N_2+N_3 \leq 300000$
- $0 \leq M \leq 300000$
- $1 \leq U_i \leq N$
- $1 \leq V_i \leq N$
- $U_i \neq V_i$
- All values are integers
Note that the $2$ vertices $s$ , $t$ always exist, and that because of the main paths, $G$ always has at least $3$ edges.
Input
The input is given in the following format.
$N_1$ $N_2$ $N_3$ $M$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$
Output
Output the answer to the problem in $1$ line.
Sample
Sample 1
Input
1 1 1 1 1 2
Output
4
Sample 2
Input
100000 100000 100000 0
Output
1000030000300001
There are $300003$ edges in total, and cutting can be done at any of them.
Sample 3
Input
2 2 2 3 1 4 3 6 5 2
Output
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Nachia
hotman78