結果

問題 No.3585 Make Ends Meet (Easy)
コンテスト
ユーザー detteiuu
提出日時 2026-07-10 22:07:58
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,941 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,464 ms
コンパイル使用メモリ 95,728 KB
実行使用メモリ 84,608 KB
最終ジャッジ日時 2026-07-10 22:08:06
合計ジャッジ時間 6,386 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def nC2(n):
    return n*(n-1)//2
def nC3(n):
    return n*(n-1)*(n-2)//6

def func(n):
    S = set()
    for i in range(n-1):
        for j in range(i+1, n):
            S.add((i, j))
    return S

# from collections import deque
# def solve(edge):
#     G = [[] for _ in range(N)]
#     S = func(N)
#     for u, v in edge:
#         S.remove((u, v))
#     for u, v in S:
#         G[u].append(v)
#         G[v].append(u)
#     que = deque()
#     que.append(0)
#     dist = [-1]*N
#     dist[0] = 0
#     while que:
#         n = que.popleft()
#         for v in G[n]:
#             if dist[v] == -1:
#                 dist[v] = dist[n]+1
#                 que.append(v)
#     return dist[-1]

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

limit = nC2(N)-M

if limit < N-1:
    if limit < K:
        print("No")
    else:
        print("Yes")
        ans = func(N)
        A = list(range(limit+1))
        A[K] = N-1
        for i in range(limit):
            l, r = A[i], A[i+1]
            if l > r: l, r = r, l
            ans.remove((l, r))
        for a, b in ans:
            print(a+1, b+1)
    exit()

right = N-K
if nC2(right+1)+(N-1-right) < limit:
    print("No")
else:
    print("Yes")
    ans = []
    for i in range(right):
        for j in range(i+1, right+1):
            ans.append((i, j))
    for i in range(right, N-1):
        ans.append((i, i+1))
    IDX = list(range(N))
    dist = [0]
    for _ in range(right):
        dist.append(1)
    for _ in range(N-right-1):
        dist.append(dist[-1]+1)
    for i in reversed(range(N)):
        if dist[i] == K:
            IDX[i], IDX[N-1] = IDX[N-1], IDX[i]
            break
    cnt = len(ans)-limit
    ans2 = func(N)
    for a, b in ans:
        if (b <= right and (a, b) != (0, right)) and cnt:
            cnt -= 1
        else:
            l, r = IDX[a], IDX[b]
            if l > r: l, r = r, l
            ans2.remove((l, r))
    for a, b in ans2:
        print(a+1, b+1)
0