No.630 Kadomatsu Graph
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.
- $x_1,x_2,x_3$ are all distinct.
- 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もしくは右上の雲マークをクリックしてアカウントを作成してください。
はむこ