스테이션

싱가포르 인터넷 백본(SIB)은 $n$개의 스테이션으로 이루어져 있으며, 각 스테이션에는 $0$부터 $n-1$까지의 인덱스가 부여된다. 또한 $n-1$개의 양방향 링크가 $0$부터 $n-2$까지 번호가 매겨져 있다. 각 링크는 서로 다른 두 스테이션을 연결한다. 하나의 링크로 연결된 두 스테이션을 이웃이라고 한다.

스테이션 $x$에서 스테이션 $y$로 가는 경로는 서로 다른 스테이션의 나열 $a_0,a_1,\cdots,a_p$로, $a_0=x$, $a_p=y$이고 경로에서 연속한 두 스테이션은 모두 이웃이다. 임의의 스테이션 $x$에서 다른 스테이션 $y$로 가는 경로는 정확히 하나 존재한다.

임의의 스테이션 $x$는 패킷(데이터 조각)을 만들어 다른 스테이션 $y$로 보낼 수 있으며, $y$를 패킷의 목적지라고 한다. 이 패킷은 $x$에서 $y$로 가는 유일한 경로를 따라 다음과 같이 라우팅되어야 한다. 현재 패킷을 가지고 있고 패킷의 목적지가 $y$인 스테이션 $z$($z \neq y$)를 생각하자. 이때 스테이션 $z$는 1. $z$에서 $y$로 가는 유일한 경로 위에 있는 $z$의 이웃을 결정하는 라우팅 절차를 실행하고, 2. 이 이웃에게 패킷을 전달한다.

그러나 스테이션은 메모리가 제한되어 있어 SIB의 전체 링크 목록을 저장하고 라우팅 절차에 사용할 수 없다.

여러분의 과제는 SIB를 위한 라우팅 방식을 구현하는 것이며, 이는 두 개의 절차로 이루어진다.

• 첫 번째 절차는 $n$, SIB의 링크 목록, 정수 $k \geq n-1$을 입력으로 받는다. 이 절차는 각 스테이션에 $0$부터 $k$까지의 서로 다른 정수 레이블을 부여한다.

• 두 번째 절차는 라우팅 절차로, 레이블이 부여된 후 모든 스테이션에 배치된다. 이 절차는 오직 다음 입력만 받는다:

  • 현재 패킷을 가지고 있는 스테이션의 레이블 $s$,
  • 패킷의 목적지 스테이션의 레이블 $t$ ($t \neq s$),
  • $s$의 모든 이웃의 레이블 목록 $c$.

  이 절차는 패킷을 전달해야 할 $s$의 이웃의 레이블을 반환해야 한다.

한 부분과제에서는 여러분의 풀이 점수가 임의의 스테이션에 부여된 레이블의 최댓값에 따라 달라진다. 일반적으로 작을수록 좋다.

• $1 \leq r \leq 10$

label을 호출할 때마다:

• $2 \leq n \leq 1000$
• $k \geq n-1$
• $0 \leq u[i], v[i] \leq n - 1$ (모든 $0 \leq i \leq n - 2$에 대해)

find_next_station을 호출할 때마다, 입력은 이전에 호출된 label 중 임의로 선택된 호출에서 나온다. 그 호출이 만들어 낸 레이블을 생각하자. 그러면:

• $s$와 $t$는 서로 다른 두 스테이션의 레이블이다.
• $c$는 레이블이 $s$인 스테이션의 모든 이웃의 레이블을 오름차순으로 나열한 수열이다.

각 테스트 케이스에서 find_next_station 절차에 전달되는 모든 배열 $c$의 길이의 합은 모든 시나리오를 합쳐 $100\;000$을 넘지 않는다.