Spanning trees in random satisfiability problem