A communication problem about graphs


An undirected graph on $n$ vertices and $n-1$ edges $G = (V,E)$ is partitioned between two players $A$ and $B$ such that $A$ knows $(V,E_A)$, $B$ knows $(V,E_B)$ and $E_A dotcup E_A = E$.

Initially, $B$ receives an advice $m_1$ that depends on $G$ and the given partition. After that, $B$ receives a randomized message $m_2$ from $A$, and has to decide whether $G$ is connected or not. If $G$ is connected, then there should be an advice $m_1$ such $B$ will accept with probability at least $2/3$. If it does not, then for any given advice $m_1$, $B$ will accept with probability at most $1/3$.

Is it possible to achieve such a protocol with $m_1 = o(n)$ and $m_2 = o(n)$?