아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

K번째 최단 경로

시간 제한1초메모리 제한512 MB

요약
각 자릿수가 정확히 1만큼 다른 L자리 수끼리 연결된 그래프에서 x에서 y로 가는 최단 경로를 사전순으로 정렬해 K번째 경로를 구하거나, 없으면 NO를 출력한다.
난이도

보통10점 중 7점

유형
그래프, BFS, 조합론, 최단 경로
정답자
아직 제출이 없습니다

문제

Bob와 Alice는 그래프에서 최단 경로를 찾는 게임을 즐겨한다.

동생 Bob은 아직 어려서 실수를 많이 하기 때문에 Alice는 Bob가 연습할 수 있도록 다음과 같은 문제를 제시했다.

먼저, 길이를 나타내는 정수 LL을 정한 후, 00부터 10L−110^L-1 까지의 총 10L10^L개의 양의 정수를 이용하여 아래 규칙에 따라 그래프를 만든다:

  • 노드: 00부터 10L−110^L-1 까지의 각 정수는 그래프의 고유한 노드를 나타낸다. 이 때, 각 정수는 선행하는 00을 붙여 반드시 길이가 LL이 되도록 만든다. 예를 들어 L=2L = 2라면 00,01,02,…,98,9900, 01, 02, \dots, 98, 99로 총 100100개의 노드를 만들게 된다.
  • 간선: 두 정점 (x,y)(x, y) 사이에 간선이 있으려면 xx와 yy의 11의 자리, 1010의 자리, ..., 10L−110^{L-1}의 자리를 비교했을 때 딱 한 곳만 달라야 하고 그 차이가 정확히 11이 되어야 한다. 예를 들어 L=2L = 2인 경우, 0000과 0101, 0101과 1111, 2727과 3737, 3636과 4646 사이에는 간선이 있고, 0000과 0202, 0101과 1010, 3636과 4747 혹은 4646과 5757사이에는 간선이 없다.

아래 그림은 L=2L = 2 인 경우 그래프의 일부를 보여준다.

위 규칙에 따라 그래프를 만든 뒤, Alice는 Bob에게 두 정점 xx와 yy사이의 최단 경로 중 사전 순으로 정렬했을 시 KK번째에 해당하는 최단 경로를 찾아보라고 했다. 예를 들어 L=2L = 2, x=37x = 37, y=55y = 55인 경우를 생각해보자. 이 경우 두 노드 사이의 최단 거리는 44이며, 아래와 같이 총 여섯 개의 최단 경로가 존재한다. 만약 K=3K = 3이라면 정답은 33번째 최단 경로인 37−36−46−56−5537 - 36 - 46 - 56 - 55가 된다.

  1. 37−36−35−45−5537 - 36 - 35 - 45 - 55
  2. 37−36−46−45−5537 - 36 - 46 - 45 - 55 위의 경로와 비교하면 33번째 노드인 3535가 4646보다 사전 순으로 앞선다.
  3. 37−36−46−56−5537 - 36 - 46 - 56 - 55 위의 경로와 비교하면 44번째 노드인 4545가 5656보다 사전 순으로 앞선다.
  4. 37−47−46−45−5537 - 47 - 46 - 45 - 55 위의 경로와 비교하면 22번째 노드인 3636이 4747보다 사전 순으로 앞선다.
  5. 37−47−46−56−5537 - 47 - 46 - 56 - 55 위의 경로와 비교하면 44번째 노드인 4545가 5656보다 사전 순으로 앞선다.
  6. 37−47−57−56−5537 - 47 - 57 - 56 - 55 위의 경로와 비교하면 33번째 노드인 4646이 5757보다 사전순으로 앞선다.

입력으로 LL, KK, xx, yy가 주어졌을 때 Bob을 도와 xx와 yy사이의 최단 경로 중 사전 순으로 KK번째 최단 경로를 구해보자. 만약 xx와 yy사이의 최단 경로의 개수가 KK보다 작다면 "NO"를 출력하도록 한다.

입력

첫 줄에 테스트 케이스의 수 TT가 주어진다.

각 테스트 케이스의 입력은 한 줄에 LL, KK, xx, yy가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스의 정답을 각 줄에 출력한다.

KK번째 최단 경로가 존재하는 경우 해당 최단 경로를 출력하고, 그렇지 않은 경우 "NO"를 출력한다 (따옴표 제외).

제한

  • 1≤T≤151 ≤ T ≤ 15
  • 2≤L≤42 ≤ L ≤ 4
  • 1≤K≤10181 ≤ K ≤ 10^{18}
  • 0≤x,y<10L0 ≤ x, y < 10^L
  • xx, yy는 언제나 선행 00을 포함하여 길이가 LL인 형태로 주어진다.

예제2

  1. 예제 1

    입력
    7
2 1 20 22
2 2 20 22
3 3 008 258
3 22 008 258
4 10 2022 3141
4 61 2022 3141
4 1000000000000000000 0000 9999
    예상 출력
    20 21 22
NO
008 018 028 038 048 148 248 258
NO
2022 2021 3021 3031 3041 3141
NO
0000 0001 0002 1002 1012 1022 1122 1123 1133 1143 1243 2243 3243 3244 4244 4254 4354 4364 5364 6364 6464 6474 6484 6584 6684 7684 7784 7785 7786 7787 7788 7888 7988 8988 8998 9998 9999

  2. 예제 2

    입력
    7
2 1 37 55
2 2 37 55
2 3 37 55
2 4 37 55
2 5 37 55
2 6 37 55
2 7 37 55
    예상 출력
    37 36 35 45 55
37 36 46 45 55
37 36 46 56 55
37 47 46 45 55
37 47 46 56 55
37 47 57 56 55
NO