You are given a simple connected graph with $$$n$$$ vertices and $$$n$$$ edges. A graph is beautiful if all of its connected components are trees of size $$$4$$$. A graph is good if a set of edges can be deleted from the graph to make it beautiful. For each of the $$$n$$$ edges, output whether the graph formed without the edge is good.
In the example above, since the red edges can be deleted to make the resulting graph *beautiful*, the graph above is an example of a *good* graph.
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10)$$$, representing the number of test cases.
The first line of each test case contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$.
The following $$$n$$$ lines describe the edges. The $$$i$$$th line contains two integers $$$u_i$$$ and $$$v_i$$$ $$$(1 \leq u_i, v_i \leq n, u_i \neq v_i)$$$ such that vertices $$$u_i$$$ and $$$v_i$$$ are connected by an edge.
It is guaranteed that the edges of each test case forms a connected graph and that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$
For each testcase, output a binary string of length $$$n$$$. The $$$i$$$-th character should be $$$1$$$ if the resulting graph after the $$$i$$$th edge is good and $$$0$$$ if it is not.
| Subtask | Constraint | Points |
| $$$1$$$ | $$$\sum n \leq 3000$$$ | $$$60$$$ |
| $$$4$$$ | No additional constraints | $$$90$$$ |
2 4 1 2 2 3 3 4 4 1 8 1 2 2 3 3 4 4 5 5 6 6 7 2 7 6 8
1111 00110110
In the first test case, removing any edge would result in a chain of size $$$4$$$, which is beautiful.
The graph of the second test case is shown in the image above.