問題一覧 > 通常問題

No.630 Kadomatsu Graph

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 256 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 78
作問者 : mai / テスター : はむこ
お気に入りにしたユーザー ProblemId : 1726 / 自分の提出
問題文最終更新日: 2025-02-10 00:17:23
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 179 (順位表) の他の問題:

Definitions

A sequence $x = (x_1,x_2,x_3)$ of 3 natural numbers is called a Kadomatsu sequence when $x$ satisfies the following conditions.

  1. $x_1,x_2,x_3$ are all distinct.
  2. Among the 3 elements, $x_2$ is the largest or the smallest.

A way of going from one vertex to another, where the start and end points are different and every vertex is visited at most once, is called a path.
A path of length 2 is a path consisting of 2 edges and 3 vertices.

In addition, this problem defines what is called a Kadomatsu path.
Let $x=(x_1,x_2,x_3)$ be the numbers written on the vertices of a path of length 2, in order from its start point to its end point. When $x$ is a Kadomatsu sequence, the path is called a Kadomatsu path.


Problem Statement

You are given $N$ and $M$.

Determine whether a graph satisfying the following conditions (a Kadomatsu graph) can be constructed, and if it can, output that graph.

  • It has $N$ vertices and $M$ edges.
  • A natural number $a_i$ is written on vertex $i$.
  • Edge $j$ is incident to vertex $u_j$ and vertex $v_j$.
  • The graph is connected and has no multiple edges or self-loops.
  • Every path of length 2 you pick is a Kadomatsu path.

Input

$N$ $M$

$3 \le N \le 10^5$
$2 \le M \le 10^5$

Natural numbers are given.

Output

$S$
$a_1$ $\ldots$ $a_N$
$u_1$ $v_1$
$\ldots$
$u_M$ $v_M$

$S \in \{\text{YES},\text{NO}\}$
$1 \le a_i \le 10^5$
$1 \le u_j,v_j \le N$

When you output a number, output a natural number.
Represent vertices as 1-indexed.

If a graph satisfying the constraints cannot be constructed, output "NO" on line 1.

If a graph satisfying the constraints can be constructed, output "YES" on line 1, and output the information of the graph from line 2 onward.


This problem uses a special judge. There are multiple outputs that satisfy the conditions, and any of them will be accepted.

Sample

Sample 1
Input
6 6
Output
YES
5 1 4 2 3 4
1 2
2 3
3 4
1 4
1 5
1 6

Drawing the graph shown in the output gives the figure above.
You can confirm that every path of length 2 you pick is a Kadomatsu path.
Therefore, a Kadomatsu graph satisfying the conditions $N=6,M=6$ exists.

Sample 2
Input
10 8
Output
NO

The answer is NO because a connected graph cannot be made.

Sample 3
Input
10 30
Output
NO

It cannot be done.

Sample 4
Input
7 8
Output
YES 
1 2 3 4 5 6 7 
1 4
2 4
2 5
3 5
3 6
3 7
1 5
1 6

It can be done.

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