This is the hard version of the problem. The difference between the versions is that in this version, the constraint on (n) is higher. You can hack only if you solved all versions of this problem. You once had an undirected tree with (n) nodes. To make the tree look more interesting, you decided to assign an arbitary direction to each of the (n-1) edges. As time goes by, you forgot the structure of your tree. However, you found a note which recorded after the direction of the edges have been assigned, whether (u) can reach (v)(^{\text{∗}}) for all ordered pairs of ((u,v)) which satisfies (1\le u,v\le n). You want to find out the structure of the tree and the direction of the edges from the information given by the note. Determine if there is possible solution and construct one. If there are multiple solutions, you only need to find one of them. (^{\text{∗}})For a directed graph, we say that (x) can reach (y) if and only if there exists a sequence of nodes (u_1,u_2,\ldots,u_k) such that (u_1=x,u_k=y) and for all (i) from (2) to (k), the directed edge (u_{i-1}\rightarrow u_i) exists. In particular, a node can always reach itself. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test cases contain an integer (n) ((2\le n\le 8000)) denoting the number of nodes your tree have. The following (n) lines contain a string (s_i). (s_i) is of length (n) and consists only of (0) and (1). The (j)-th character of (s_i) is (1) if and only if (i) can reach (j) after the edges are directed. It is guaranteed that the sum of (n^2) over all test cases does not exceed (8000^2). For each testcase, output (Yes) if a solution exists, otherwise print (No). If the answer is (Yes),