# 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)$$?