問題一覧 > 通常問題

No.2160 Three Dominators

レベル : / AI推定難易度 : 2800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 16
作問者 : 👑 Nachia / テスター : hotman78
お気に入りにしたユーザー ProblemId : 8234 / 自分の提出
問題文最終更新日: 2022-12-10 16:29:30
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2022 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。