// Spreading Gossip (mjd@cs.auckland.ac.nz)
//
#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

typedef vector<int> NLIST;    		// node (neighbor) list
typedef vector< NLIST > ADJLIST;  	// graph data structure

class Graph
{
private:

   ADJLIST adj;  // adjacency lists.

public:  
   // creators + destroyers
   //
   Graph(int n) : adj(n) { }
   ~Graph() {}

   // stream I/0
   //
   friend ostream& operator<<(ostream&, const Graph&);
   friend istream& operator>>(istream&, Graph&);

   // mutators
   //
   bool addEdge(int u, int v)  // false if already exists
   {
     if ( isEdge(u,v) ) return false;
  
     adj[u].push_back(v);
     return true;
   }
   bool rmEdge(int u, int v)  // false if doesn't exist
   {
     int n = order();

     const NLIST::iterator it = find( adj[u].begin(), adj[u].end(), v );
     if ( it==adj[u].end() ) return false;
     adj[u].erase(it);
     return true;
   }

   // accessors
   //
   int order() const { return adj.size(); }

   bool isEdge(int u, int v) const
   {
     int n = order();
     NLIST::const_iterator it = find( adj[u].begin(), adj[u].end(), v );
     if ( it==adj[u].end() ) return false;
     else return true;
   }

   bool isUndirected() const 
   {
     int n=order();
     for (int i=0; i<n-1; i++)
      for (int j=i+1; j<n; j++)
        if (isEdge(i,j) != isEdge(j,i)) return false;
     return true;
   }

   int degree(int u) const { return adj[u].size(); }

   const NLIST neighbors(int u) const { return (const NLIST&) adj[u]; }
};

ostream& operator<<(ostream& o, const Graph& G)
{
  o << G.order() << "\n";
  for (int i=0; i<G.order(); i++) 
  {
    for (unsigned int j=0; j<G.adj[i].size(); j++) o << G.adj[i][j] << " ";
    o << "\n";
  }
  return o;
}

const static int LLEN=1024;
//
istream& operator>>(istream& in, Graph& G) 
{
   char line[LLEN];
   int n;
   in.getline(line, LLEN);
   istringstream lineIn(line);
   lineIn >> n;

   G.adj.resize(n);
   for (int i=0; i<n; i++) 
   {
     G.adj[i].resize(0);
   }

   for (int v1=0; v1<n; v1++)
   {
      in.getline(line, LLEN);    
      istringstream lineIn(line);
      int v2; while (lineIn>>v2)
      { 
        G.addEdge(v1,v2);
      }
   }
   return in;
}

static int ORIG_VERT = 0;

struct BroadcastState
{
  int time; // if time >= 0 update time.
  int node;  // if time == -1 then this "node" broadcasts
  int neighbor;  // to this "neighbor"

  int operator==(const BroadcastState &s) const
  {
    return time == s.time && node == s.node && neighbor == s.neighbor;
  }
};

ostream& operator<<(ostream& o, const BroadcastState &s)
{
  //return o;
  if (s.time >= 0)  return o << "time=" << s.time;
  return o << s.node << " -> N(" << s.neighbor << ")";
}

typedef stack< BroadcastState > BroadcastTree;

// --------------- find broadcast scheme ------------
//
int broadcast(const Graph &G, vector<int> &mesg)
{
  int n=G.order();
  int best;  // best-known broadcast time

  fill(mesg.begin(), mesg.end(), n);

  BroadcastTree btree; // 2*n
  BroadcastState bstate;

  // end of search record
  bstate.time = 0;
  btree.push(bstate);

  // first broadcast
  //
  mesg[ORIG_VERT] = 0;  // originator has time 0
  mesg[G.neighbors(ORIG_VERT)[0]] = 1;
  //
  bstate.time = 1;
  btree.push(bstate);
  // 
  bstate.time = -1;
  bstate.node = ORIG_VERT;
  bstate.neighbor = 0;
  btree.push(bstate);

  int have = 2; 
  int time = 1;

  // grow first broadcast tree
  //
  while (have < n)
  {
    time++;

    bstate.time = time;
    btree.push(bstate);

    for (int i=0; i<n; i++)
    {
       if (mesg[i] < time)  // can this node broadcast?
       {
           int indexTryFirst = 0;
           int indexTry = indexTryFirst;
           //
           do
           {
             if ( mesg[G.neighbors(i)[indexTry]] == n )
             {
               mesg[G.neighbors(i)[indexTry]] = time;
               have++;

               bstate.time = -1;
               bstate.node = i;
               bstate.neighbor = indexTry;
               btree.push(bstate);
                
               break;
             }
   
             indexTry = (indexTry + 1) % G.degree(i);   

           } while (indexTry != indexTryFirst);

       }
    }
  }

while(1) // loop until backtrack stops
{
  best = time;

  // backtrack phase one level
  //
  while (time == best)
  {
    bstate = btree.top(); btree.pop();

    if (bstate.time < 0)
    {
      mesg[G.neighbors(bstate.node)[bstate.neighbor]] = n;
      have--;
    }
    else time = bstate.time-1;  // i.e. best-1 
  }

  bool back = true;
  int startI = 0;

 while (have < n)
 {
  if (back)
  {
    bstate = btree.top(); btree.pop();
  
    if (bstate.time < 0)
    {
      mesg[G.neighbors(bstate.node)[bstate.neighbor]] = n;
      have--;

      // look for another neighbor to broadcast
      //
      for (int j=bstate.neighbor+1; j<G.degree(bstate.node); j++) // degree
      {
        if ( mesg[G.neighbors(bstate.node)[j]] == n )
        {
          mesg[G.neighbors(bstate.node)[j]] = time;
          have++;
          bstate.neighbor = j;
          btree.push(bstate);
            
          back = false;      
          startI = bstate.node+1;
          break;
        }
      }
    }
    else 
    {
     time = bstate.time-1;
     if (time < 0) return best;
     continue;
    }

  }
  else // ! back
  {
    if (time+(startI==0) >= best) { back = true; continue; }

    if (startI==0)
    {
      time++;
      bstate.time = time;
      btree.push(bstate);
    }

    for (int i=startI; i<n; i++)
    {
       if (mesg[i] < time)  // can this node broadcast?
       {
           int indexTryFirst = 0;
           int indexTry = indexTryFirst;
           //
           do
           {
             if ( mesg[G.neighbors(i)[indexTry]] == n )
             {
               mesg[G.neighbors(i)[indexTry]] = time;
               have++;

               bstate.time = -1;
               bstate.node = i;
               bstate.neighbor = indexTry;
               btree.push(bstate);
                
               break;
             }
   
             indexTry = (indexTry + 1) % G.degree(i);   

           } while (indexTry != indexTryFirst);

       }
    }
    
    startI=0;

   } // forward
 }

} 
}

//******************************************************************
//
int main(int argc, char **argv)
{
  int graphCount = 1;
  //
  if (argc > 1) ORIG_VERT = atoi(argv[1]);

  // ---------------  read in regular graph -----------------
  //
  Graph G(0);

while (1)
  {
  cin >> G; if (! G.order() ) break;
  if (G.isUndirected()==false) cerr << "Not undirected graph!\n";
  cout << "Village " << (graphCount++);

  int n=G.order();
  vector<int> mesg(n);
  int bestTime = broadcast(G, mesg);

  cout << ": " << bestTime << "\n";

 } // end of stream of graphs
}