問題一覧 > 通常問題

No.488 Square Relationship

レベル : / AI推定難易度 : 500 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 244
作問者 : 小指が強い人 / テスター : tatuyan_edson
お気に入りにしたユーザー ProblemId : 979 / 自分の提出
問題文最終更新日: 2026-06-25 11:37:27
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
yukicoder contest 157 (順位表) の他の問題:

Problem Statement

$N$ nodes are numbered from $0$ to $N-1$.
Some nodes have relationships with each other, and some do not.
Output the number of square relationships in this set of nodes.
Here, a square relationship means that, when considering only those 4 nodes, they form a cycle graph on $4$ vertices.
(That is, no cycle can be formed by 3 of those 4 points.)

Input

$N$ $M$
$a_1$ $b_1$
$a_2$ $b_2$
$⋮$  $⋮$
$a_{M-1}$ $b_{M-1}$
$a_M$ $b_M$

$N$ is the number of nodes.
$M$ is the number of pairs of nodes that have a relationship.
$a_i$ and $b_i$ are node numbers, indicating that $a_i$ and $b_i$ have a relationship.
$2 \le N \le 50$ (integer)
$1 \le M \le \frac{N \times (N - 1)}{2}$ (integer)
$0 \le a_i < b_i < N$ (integer)
$(a_i,b_i) \ne (a_j,b_j)$
$i=1...M$

Output

$X$

Output one value, the answer to the problem.

Sample

Sample 1
Input
6 8
0 1
1 2
2 3
0 2
0 3
3 4
4 5
0 5
Output
1


The figure above shows the node relationships in Sample 1.
There are two candidates, {0,1,2,3} and {0,3,4,5}, but {0,1,2,3} is excluded because 0 and 2 have a relationship.
Therefore, the answer is 1.

Sample 2
Input
3 3
0 1
1 2
0 2
Output
0

With 3 nodes, there can be no square relationship.

Sample 3
Input
8 17
0 3
0 4
0 6
1 2
1 6
2 4
2 5
2 7
3 4
3 5
3 6
4 5
4 6
4 7
5 6
5 7
6 7
Output
3


The 3 sets {1,2,5,6}, {1,2,7,6}, and {1,2,4,6} satisfy the condition.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。