  Given a connected graph $G$ and its vertex $x$, let $U_x(G)$ denote the
universal cover of $G$ obtained by unfolding $G$ into a tree starting from $x$.
Let $T=T(n)$ be the minimum number such that, for graphs $G$ and $H$ with at
most $n$ vertices each, the isomorphism of $U_x(G)$ and $U_y(H)$ surely follows
from the isomorphism of these rooted trees truncated at depth $T$. Motivated by
applications in theory of distributed computing, Norris [Discrete Appl. Math.
1995] asks if $T(n)\le n$. We answer this question in the negative by
establishing that $T(n)=(2-o(1))n$. Our solution uses basic tools of finite
model theory such as a bisimulation version of the Immerman-Lander 2-pebble
counting game.
  The graphs $G_n$ and $H_n$ we construct to prove the lower bound for $T(n)$
also show some other tight lower bounds. Both having $n$ vertices, $G_n$ and
$H_n$ can be distinguished in 2-variable counting logic only with quantifier
depth $(1-o(1))n$. It follows that color refinement, the classical procedure
used in isomorphism testing and other areas for computing the coarsest
equitable partition of a graph, needs $(1-o(1))n$ rounds to achieve color
stabilization on each of $G_n$ and $H_n$. Somewhat surprisingly, this number of
rounds is not enough for color stabilization on the disjoint union of $G_n$ and
$H_n$, where $(2-o(1))n$ rounds are needed.
