  Two mobile agents, starting from different nodes of an $n$-node network at
possibly different times, have to meet at the same node. This problem is known
as rendezvous. Agents move in synchronous rounds using a deterministic
algorithm. In each round, an agent decides to either remain idle or to move to
one of the adjacent nodes. Each agent has a distinct integer label from the set
$\{1,...,L\}$, which it can use in the execution of the algorithm, but it does
not know the label of the other agent.
  If $D$ is the distance between the initial positions of the agents, then
$\Omega(D)$ is an obvious lower bound on the time of rendezvous. However, if
each agent has no initial knowledge other than its label, time $O(D)$ is
usually impossible to achieve. We study the minimum amount of information that
has to be available a priori to the agents to achieve rendezvous in optimal
time $\Theta(D)$. This information is provided to the agents at the start by an
oracle knowing the entire instance of the problem, i.e., the network, the
starting positions of the agents, their wake-up rounds, and both of their
labels. The oracle helps the agents by providing them with the same binary
string called advice, which can be used by the agents during their navigation.
The length of this string is called the size of advice. Our goal is to find the
smallest size of advice which enables the agents to meet in time $\Theta(D)$.
We show that this optimal size of advice is $\Theta(D\log(n/D)+\log\log L)$.
The upper bound is proved by constructing an advice string of this size, and
providing a natural rendezvous algorithm using this advice that works in time
$\Theta(D)$ for all networks. The matching lower bound, which is the main
contribution of this paper, is proved by exhibiting classes of networks for
which it is impossible to achieve rendezvous in time $\Theta(D)$ with smaller
advice.
