No.3012 岩井星人グラフ
タグ : / 解いたユーザー数 225
作問者 : 👑





問題文
$3$ 以上の整数 $X, Y$ が与えられます。以下のように説明される腕の本数 $X,$ 腕の長さ $Y$ の岩井星人グラフを $1$ つ出力してください。
- $XY$ 個の頂点と $XY$ 本の辺からなる単純無向グラフである。
- 次数 $1$ の頂点が $X$ 個、次数 $2$ の頂点が $X (Y - 2)$ 個、次数 $3$ の頂点が $X$ 個ある。
- 任意の次数 $1$ の頂点 $v$ について、頂点 $v$ からの距離が最も短い次数 $3$ の頂点との距離が $Y - 1$ である。
具体例は下記のサンプルを参考にしてください。
ただし、本問題の制約下ではそのような岩井星人グラフは複数存在しますが、それらのいずれを出力しても正解と判定されます。
単純無向グラフとは
単純無向グラフとは、単純で辺に向きの無いグラフのことをいいます。
グラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。
次数とは
頂点の次数とは、その頂点から出ている辺の本数のことをいいます。
制約
- $3 \le X, Y \le 500$
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
$X$ $Y$
出力
答えとなる腕の本数 $X, $ 腕の長さ $Y$ の岩井星人グラフが以下のように説明されるとする。
- $n$ 個の頂点からなり、各頂点には $1$ から $n$ までの番号が振られている。
- $m$ 本の辺からなり、各辺には $1$ から $m$ までの番号が振られている。
- 各 $i ~ (1 \le i \le m)$ について、辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を結ぶ。
このとき、以下の形式で出力せよ。ただし、本問題の制約下では答えが複数存在するが、それらのいずれを出力しても正解と判定される。
$n$ $m$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_{m}$ $v_{m}$
サンプル
サンプル1
入力
3 3
出力
9 9 1 6 2 4 3 5 4 9 5 7 6 8 7 8 8 9 9 7
以下のようなグラフが腕の本数 $3,$ 腕の長さ $3$ の岩井星人グラフの一例です。
このグラフについて、以下のことがいえます。ここで、$X = 3, ~ Y = 3$ です。
- $9$ 個の頂点と $9$ 本の辺からなる単純無向グラフである。$(XY = 9)$
- 次数 $1$ の頂点は、頂点 $1, 2, 3$ の $3$ 個 $(X = 3)$ ある。
- 次数 $2$ の頂点は、頂点 $4, 5, 6$ の $3$ 個 $(X(Y - 2) = 3)$ ある。
- 次数 $3$ の頂点は、頂点 $7, 8, 9$ の $3$ 個 $(X = 3)$ ある。
- それぞれの次数 $1$ の頂点について、以下のことが言える。
- 頂点 $1$ との距離が最も短い、次数 $3$ の頂点は頂点 $8$ である。その距離は $2 ~ (Y - 1 = 2)$ である。
- 頂点 $2$ との距離が最も短い、次数 $3$ の頂点は頂点 $9$ である。その距離は $2$ である。
- 頂点 $3$ との距離が最も短い、次数 $3$ の頂点は頂点 $7$ である。その距離は $2$ である。
サンプル2
入力
5 4
出力
20 20 1 2 1 5 1 6 2 3 2 9 3 4 3 12 4 5 4 15 5 18 6 7 7 8 9 10 10 11 12 13 13 14 15 16 16 17 18 19 19 20
以下のようなグラフが腕の本数 $5,$ 腕の長さ $4$ の岩井星人グラフの一例です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。