# Rik, the Space Traveler

Mr. Rik is a famous space traveler. He lives in a galaxy named Victa. There are many planets in this galaxy. Rik doesn’t travel all the planets. He only travels the planets which are numbered from 1 to n. The planets are connected by bidirectional space tunnels. The fare of these space tunnels is so cheap. If planet u and planet v are connected by a space tunnel, only 1 gk needs to be paid to travel from u to v or from v to u. Here, “gk” is the name of the currency of the galaxy Victa. Rik starts traveling from a planet x with k gk in his moneybag. He can visit a planet for more than one time. Whenever he uses a space tunnel, 1 gk decreases from his moneybag. If the amount of money in his moneybag becomes 0 gk on a planet y, he stops traveling. Rik knows that there can be more than one planet y for a starting planet x and there can be many ways to travel. Two ways are different if the traversed planets are different or the traversal orders of the planets are different. Planets numbered from 1 to n also have a special characteristic. For any two of these planets u and v, it is always possible to travel from u to v or from v to u if Rik has enough gk.

This is a companion discussion topic for the original entry at https://toph.co/p/rik-the-space-traveller