結果

問題 No.3585 Make Ends Meet (Easy)
コンテスト
ユーザー detteiuu
提出日時 2026-07-10 22:18:33
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,518 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 241 ms
コンパイル使用メモリ 95,856 KB
実行使用メモリ 86,656 KB
最終ジャッジ日時 2026-07-10 22:18:41
合計ジャッジ時間 7,198 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]

from random import randrange

N, M, K = map(int, input().split())
# N = randrange(2, 11)
# M = randrange(nC2(N)+1)
# K = randrange(1, N)
# print(N, M, K)

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)
        # print(solve(ans) == K)
    exit()

right = N-K
if K == 2:
    print("Yes")
    ans = [(0, N-2), (N-2, N-1)]
    for i in range(N-1):
        if len(ans) == limit:
            break
        for j in range(i+1, N):
            if len(ans) == limit:
                break
            if (i, j) not in [(0, N-1), (0, N-2), (N-2, N-1)]:
                ans.append((i, j))
    ans2 = func(N)
    for a, b in ans:
        ans2.remove((a, b))
    for a, b in ans2:
        print(a+1, b+1)
elif 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)
    # print(solve(ans2) == K)
0