In this paper, we consider a network reconstruction problem using UAVs where stationary ad-hoc networks are severely damaged in a post-disaster scenario. The main objective of this paper is to repair network by supplementing aerial wireless links into the stationary network to reconnect isolated ground networks each other with a limited number of UAVs. We propose a distributed motion planning that guarantees complete coverage to probe network connectivity from the air over stationary networks, while reducing duplicate coverage with other UAVs. Given the collected local connectivity information over region of interest, we deploy UAVs as relays into the locations of network holes to repair network-wide data delivery most effectively by formulating the problem into a binary integer program. Simulation results show that our network traversing algorithm outperforms a multi-agent exploration algorithm Ants in terms of complete coverage time, travel distance, and duplicate coverage. Also, our deployment optimization enhances network-wide routing performance compared to a practical baseline counterpart.