Keyring Order - Repovive Starter Round 8 | Repovive

23G. Keyring Order

3500 pts2s256 MB

You are given a tree with $n$ vertices, numbered from $1$ to $n$ . There is a closed door on every edge.

Each door has exactly one key. These keys are divided among $m$ nonempty keyrings, numbered from $1$ to $m$ . You carry all the keyrings from the beginning.

You choose a starting vertex. You may move through open doors in either direction any number of times. If you are at either endpoint of an edge with a closed door, you may use its key to open it. Once opened, a door remains open forever.

You may use the keyrings in any order. However, once you open a door using a keyring, you must open every door whose key belongs to that keyring before you can open a door using another keyring. You may choose the order of the keys within each keyring.

For every vertex, determine whether it is possible to open all the doors when starting there.

Output a binary string $s$ of length $n$ , where $s_i$ is $1$ if starting at vertex $i$ is possible, and $0$ otherwise.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le m < n$
$1 \le u_i,v_i \le n$ , $u_i \ne v_i$
$1 \le c_i \le m$
The given edges form a tree.
Every keyring contains at least one key: each number from $1$ to $m$ appears among $c_1,c_2,\ldots,c_{n-1}$ .
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \quad c_1 \\ u_2 \quad v_2 \quad c_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \quad c_{n-1} \end{array} \right\} \times t

Each triple $u_i,v_i,c_i$ describes an edge between vertices $u_i$ and $v_i$ whose door has its key on keyring $c_i$ .

Output

\left. \begin{array}{l} s \end{array} \right\} \times t

For each test case, output one binary string $s$ of length $n$ , without spaces between its characters.

Samples

Input

Case 1

2 1
1 2 1

Case 2

Explanation

Case 1

Starting at either endpoint, you can open the only door.

Case 2

Starting at vertex 3, 4, or 7, you can open both doors of keyring 3, then both doors of keyring 2, and finally both doors of keyring 1. From vertex 2 or 5, neither adjacent keyring can be completed before switching keyrings. From vertex 1 or 6, the first door forces you to start keyring 1, but its other door cannot yet be reached.

Output

Case 1

Case 2

Input

Case 1

Case 2

Case 3

Explanation

Case 1

The two doors of either keyring are separated by a door of the other keyring. Whichever keyring you start with, you cannot finish it without first using the other one. No starting vertex works.

Case 2

Starting at vertex 2 or 3, open the door of keyring 2 first, then the two doors of keyring 1. Starting at vertex 1 or 4 forces keyring 1 first, but its other door is unreachable without using keyring 2.

Case 3

Every starting vertex works. From a leaf, first finish the keyring of its incident door; all its doors can be reached through vertex 1. You can then finish each remaining keyring. Starting at vertex 1 also allows any order of keyrings.

Output

Case 1

Case 2

Case 3

You are given a tree with $n$ vertices, numbered from $1$ to $n$ . There is a closed door on every edge.

Each door has exactly one key. These keys are divided among $m$ nonempty keyrings, numbered from $1$ to $m$ . You carry all the keyrings from the beginning.

For every vertex, determine whether it is possible to open all the doors when starting there.

Output a binary string $s$ of length $n$ , where $s_i$ is $1$ if starting at vertex $i$ is possible, and $0$ otherwise.

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le m < n$
$1 \le u_i,v_i \le n$ , $u_i \ne v_i$
$1 \le c_i \le m$
The given edges form a tree.
Every keyring contains at least one key: each number from $1$ to $m$ appears among $c_1,c_2,\ldots,c_{n-1}$ .
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \quad c_1 \\ u_2 \quad v_2 \quad c_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \quad c_{n-1} \end{array} \right\} \times t

Each triple $u_i,v_i,c_i$ describes an edge between vertices $u_i$ and $v_i$ whose door has its key on keyring $c_i$ .

\left. \begin{array}{l} s \end{array} \right\} \times t

For each test case, output one binary string $s$ of length $n$ , without spaces between its characters.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

23G. Keyring Order

Constraints

Input

Output

Samples

23G. Keyring Order

Constraints

Input

Output

Samples