만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

그래프 분해

시간 제한2초메모리 제한1024 MB

요약
n과 2n-1의 분할 a_i가 주어질 때, K_{2n}의 간선을 각 a_i-인수가 되도록 나누어 모든 간선이 정확히 한 집합에만 속하게 출력합니다.
난이도

보통10점 중 7점

유형
그래프, 조합론, 수학
정답자
아직 제출이 없습니다

문제

무방향 그래프 GG에서 rr-인수는 GG의 모든 정점을 포함하는 부분 그래프이며, GG의 간선 일부로 이루어집니다. 이때 모든 정점의 차수는 rr이어야 합니다. 이런 그래프를 rr-정규 그래프라고 합니다.

kk-정규 그래프 GG와 kk의 분할 λ\lambda, 즉 k=a1+a2+…+amk = a_1 + a_2 + \ldots + a_m을 생각합니다. GG의 λ\lambda-분해는 그래프 G1,G2,…,GmG_1, G_2, \ldots, G_m의 모임이며, 각 GiG_i는 GG의 aia_i-인수이고, GG의 모든 간선은 GiG_i 중 정확히 하나에만 속합니다.

짝수 개의 정점을 가진 완전 그래프 K2nK_{2n}과 2n−12n-1의 분할 λ\lambda가 주어질 때, K2nK_{2n}의 λ\lambda-분해를 구하세요.

입력

첫 줄에 정수 nn (1≤n≤1001 \le n \le 100)이 주어집니다. 둘째 줄에는 정수 mm과 a1,a2,…,ama_1, a_2, \ldots, a_m이 주어집니다 (1≤ai≤2n−11 \le a_i \le 2n-1, ∑ai=2n−1\sum a_i = 2n-1).

출력

mm개의 그래프를 출력하세요. GiG_i의 설명에는 nain a_i개의 간선이 있어야 합니다. 그래프 설명 사이는 빈 줄로 구분하세요.

예제1

  1. 예제 1

    입력
    3
    3 1 2 2
    
    예상 출력
    1 4
    2 5
    3 6
    
    1 2
    2 3
    3 4
    4 5
    5 6
    6 1
    
    1 3
    3 5
    5 1
    2 4
    4 6
    6 2