結果

問題 No.3585 Make Ends Meet (Easy)
コンテスト
ユーザー marc2825
提出日時 2026-05-25 07:12:33
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 99 ms / 2,000 ms
コード長 1,859 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 657 ms
コンパイル使用メモリ 21,536 KB
実行使用メモリ 15,992 KB
最終ジャッジ日時 2026-07-10 20:51:11
合計ジャッジ時間 7,124 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N, M, K = map(int, input().split())

T = N * (N - 1) // 2
E = T - M  # number of edges to keep

keep = [[False] * (N + 1) for _ in range(N + 1)]


def print_no():
    print("No")


def print_yes():
    print("Yes")

    for u in range(1, N + 1):
        for v in range(u + 1, N + 1):
            if not keep[u][v]:
                print(u, v)


if K == 1:
    # The distance is 1 iff the direct edge (1, N) remains.
    if E == 0:
        print_no()
        exit()

    keep[1][N] = True
    E -= 1

    for u in range(1, N + 1):
        if E <= 0:
            break
        for v in range(u + 1, N + 1):
            if E <= 0:
                break
            if u == 1 and v == N:
                continue

            keep[u][v] = True
            E -= 1

    print_yes()
    exit()


# K >= 2.
# Use the path 1 - 2 - ... - K - N as the mandatory shortest path.
U = N - K - 1  # number of vertices not on the path

min_keep = K
max_keep = K + 3 * U + U * (U - 1) // 2

if not (min_keep <= E <= max_keep):
    print_no()
    exit()

# Keep the mandatory path edges.
for i in range(1, K):
    keep[i][i + 1] = True
    E -= 1

keep[K][N] = True
E -= 1

free_edges = []

# Extra vertices are K+1, K+2, ..., N-1.
# Each of them can be connected to three consecutive path vertices.
for x in range(K + 1, N):
    free_edges.append((1, x))
    free_edges.append((2, x))

    if K == 2:
        # Path vertices are 1, 2, N.
        free_edges.append((x, N))
    else:
        # Path vertices include 1, 2, 3.
        free_edges.append((3, x))

# Extra vertices can be connected freely among themselves.
for x in range(K + 1, N):
    for y in range(x + 1, N):
        free_edges.append((x, y))

# Add arbitrary free edges until exactly E additional edges are kept.
for u, v in free_edges:
    if E == 0:
        break

    keep[u][v] = True
    E -= 1

print_yes()
0