이번 문제는 백트래킹을 통해 해결하였다. 친구들의 관계를 인접 리스트 형태로 저장하고, 백트래킹을 통해 탐색하였다. 문제에서 선택된 모든 친구들이 서로서로 친구관계여야 하기 때문에 백트래킹에서 다음 재귀 호출을 위해 선택하려는 친구가 선택된 친구들과 모두 친구 관계인지 확인해야 한다. 학생들의 번호 증가 순으로 가장 작은 것을 출력해야 하므로 현재 인덱스보다 큰 인덱스들을 차례대로 순회하며 아직 선택되지 않은 경우, 선택된 친구들의 친구 리스트를 확인하여 포함되어 있다면 재귀호출하도록 하였다. 그리고 정답 리스트가 한번 갱신되면, 이 값이 가장 사전순으로 빠른 오름차순 리스트이므로 함수를 return하여 가지치기를 시켰다. 이 함수를 호출하는 과정에서도 이미 결과 리스트가 갱신되어 있다면 순회를 멈추도록 하였다.

Code

k, n, f = map(int, input().split())
relation = [[] for _ in range(n+1)]
for _ in range(f):
    a, b = map(int, input().split())
    relation[a].append(b)
    relation[b].append(a)
answer = []
def find_friends(cur, friends):
    global answer
    if answer:
        return
    if len(friends) == k:
        answer = sorted(friends)
        return
    for i in range(cur+1, n+1):
        if not visited[i]:
            for num in friends:
                if num not in set(relation[i]):
                    break
            else:
                visited[i] = True
                find_friends(i, friends+[i])
for i in range(1, n+1):
    visited = [False for _ in range(n + 1)]
    visited[i] = True
    find_friends(i, [i])
    if answer:
        break
if not answer:
    print(-1)
else:
    for ans in answer:
        print(ans)