Stations

문제

Singapore's Internet Backbone (SIB) consists of $nn$ stations, which are assigned indices from $00$ to $n-1n-1$. There are also $n-1n-1$ bidirectional links, numbered from $00$ to $n-2n-2$. Each link connects two distinct stations. Two stations connected with a single link are called neighbours.

A path from station $xx$ to station $yy$ is a sequence of distinct stations $a_0,a_1,\cdots ,a_{p}a\_0,a\_1,\backslash cdots,a\_p$, such that $a_0=xa\_0=x$, $a_p=ya\_p=y$, and every two consecutive stations in the path are neighbours. There is exactly one path from any station $xx$ to any other station $yy$.

Any station $xx$ can create a packet (a piece of data) and send it to any other station $yy$, which is called the packet's target. This packet must be routed along the unique path from $xx$ to $yy$ as follows. Consider a station $zz$ that currently holds a packet, whose target station is $yy$ ($z\mathrm{\ne }yz\; \backslash neq\; y$). In this situation station $zz$: 1. executes a routing procedure that determines the neighbour of $zz$ which is on the unique path from $zz$ to $yy$, and 2. forwards the packet to this neighbour.

However, stations have limited memory and do not store the entire list of the links in SIB to use it in the routing procedure.

Your task is to implement a routing scheme for SIB, which consists of two procedures.

• The first procedure is given $nn$, the list of the links in the SIB and an integer $k\ge n-1k\; \backslash geq\; n-1$ as the inputs. It assigns each station a unique integer label between $00$ and $kk$, inclusive. 

• The second procedure is the routing procedure, which is deployed to all stations after labels are assigned. It is given only the following inputs:

  • $ss$, the label of the station that currently holds a packet,
  • $tt$, the label of the packet's target station ($t\mathrm{\ne }st\; \backslash neq\; s$),
  • $cc$, the list of the labels of all neighbours of $ss$.

  It should return the label of the neighbour of $ss$ that the packet should be forwarded to.

In one subtask, the score of your solution depends on the value of the maximum label assigned to any station (in general, smaller is better).