Note: The test data for this problem has been strengthened.

Due to data resource limitations, not all extreme cases that would fully stress-test the standard solution are included in the official test data. The standard solution runs in approximately $6.36\,\text{s}$ on the current data. Please be aware of this. However, this does not mean that solutions with incorrect complexity will always pass.

If you cannot find the optimal solution, you may want to start by considering some special properties.

Background

Before the gray tower, Tairitsu saw fragments of light.

Those fragments of light lingered around Tairitsu, like scattered flowers.

Stepping into the twisted maze, Tairitsu attempted to collect the fragments of conflict within and tried to destroy the maze.

Tairitsu was surrounded by fragments of light and conflict, crisscrossing and flying about.

Finally, Tairitsu reached the deepest part of the maze.

On that strangely shaped memory fragment, what was reflected was a memory of a world heading toward destruction.

The end of the world arrived; the sky tore apart, and the earth collapsed.

Because the "energy" carried by this fragment was so immense, Tairitsu tried to use the fragments of light and conflict around her to mitigate the massive mental shock.

Specifically, this twisted fragment forms a "tree" structure, and Tairitsu will place either a fragment of light or a fragment of conflict on each edge of the tree.

Tairitsu will cut the edges of the tree into several chains such that every edge belongs to exactly one chain. Due to the special structure of the fragment, a node in the tree can belong to multiple chains simultaneously.

Tairitsu will take a portion of the chains, merge the prefix segments that have the same fragments, and finally form a new tree, which is the so-called "Trie tree."

The more nodes this new tree has, the more it can soothe Tairitsu's emotions and help her calm down.

In her madness, Tairitsu has already placed some fragments of light or conflict on certain edges of the fragment.

In a moment of clarity, Tairitsu realized something was wrong. Therefore, Tairitsu can also choose to place either light or conflict fragments on the remaining edges arbitrarily.

In a daze, Tairitsu realized she did not know how to place and cut the edges optimally.

Her thoughts raced. What is the optimal way?

I believe you already have the answer.

Description

Given a tree with $n$ nodes, labeled $0 \sim n-1$.

The edges have weights, generally $0$ or $1$; however, some edge weights are not yet determined.

You need to determine a weight of $0$ or $1$ for each undetermined edge, and then extract several directed paths from the tree such that these chains are edge-disjoint.

Then you will insert these paths into a 0/1-Trie. You want to maximize the number of nodes in this 0/1-Trie. (Since the definition of a 0/1-Trie is quite simple, those participating in the contest should already know it, so it will not be detailed here.)

You may need to construct the specific selection scheme.

Input

This problem contains multiple test cases in each test point.

The first line contains two integers $T$ and $o$, where $T$ is the number of test cases and $o$ represents some special properties of the test point (please refer to the "Constraints" section for details).

The next $T$ lines contain the test cases.

For each test case, the first line contains an integer $n$, representing the number of nodes.

The next $n-1$ lines each contain three integers $u, v, w$, representing an edge connecting nodes $u$ and $v$. When $0 \le w \le 1$, it means the edge weight is $w$; otherwise, $w=2$, meaning the edge weight is not yet determined.

It is guaranteed that these edges form a tree with nodes $0 \sim n-1$.

Output

At the beginning, you should output a number $c$ ($c \in \{0, 1\}$), indicating whether you choose to output the construction scheme for this test point. We will use a Special Judge to verify if your output is correct. Note that this will affect the maximum score you can obtain for this test point; see the "Constraints" section for details.

For each test case, first output a single integer $A$, representing the answer for that test case.

When $c=1$, you must also output the construction scheme in the following format:

• First, output a single integer $m$, representing the number of paths in your construction.
• The next line contains $n-1$ integers, each being $0$ or $1$, representing the edge weights in the order of the input. For edges whose weights were already determined, please output them as they were.
• The next $m$ lines each contain two integers $u, v$, representing a path from $u$ to $v$ in the tree. It is required that $u \neq v$, and the paths must be edge-disjoint.

Examples

Input 1

9 0
9
1 2 1
3 4 1
5 6 1
7 8 1
2 0 0
4 0 0
6 0 0
8 0 0
9
1 2 2
3 4 1
5 6 1
7 8 1
2 0 0
4 0 0
6 0 0
8 0 0
5
1 2 2
3 4 1
0 3 1
2 3 0
17
1 2 1
2 3 0
3 4 1
4 0 0
5 6 1
6 7 0
7 8 1
8 0 0
9 10 1
10 11 0
11 12 1
12 0 0
13 14 1
14 15 0
15 16 1
16 0 0
17
1 2 1
2 0 0
3 4 1
4 0 0
5 6 1
6 0 0
7 8 1
8 0 0
9 10 1
10 11 0
11 12 1
12 0 0
13 14 1
14 15 0
15 16 1
16 0 0
17
1 2 2
2 0 2
3 4 2
4 0 2
5 6 2
6 0 2
7 8 2
8 0 2
9 10 2
10 11 2
11 12 2
12 0 2
13 14 2
14 15 2
15 16 2
16 0 2
18
1 2 1
2 0 0
3 4 1
4 0 0
5 6 1
6 0 0
7 8 1
8 0 0
9 10 1
10 11 0
11 12 1
12 0 0
13 14 1
14 15 0
15 16 1
16 0 0
0 17 2
18
1 2 2
2 0 2
3 4 2
4 0 2
5 6 2
6 0 2
7 8 2
8 0 2
9 10 2
10 11 2
11 12 2
12 0 2
13 14 2
14 15 2
15 16 2
16 0 2
17 0 2
18
1 2 2
2 3 2
3 4 2
4 5 2
5 6 2
6 7 2
7 8 2
8 9 2
9 10 2
10 11 2
11 12 2
12 13 2
13 14 2
14 15 2
15 16 2
16 17 2
17 0 2

Output 1

1
8
3
1 1 1 1 0 0 0 0
1 3
5 6
6 7
9
2
0 1 1 1 0 0 0 0
3 5
1 7
5
2
0 1 1 0
4 3
1 0
16
3
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
5 1
13 14
14 9
14
5
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
3 1
5 6
14 13
14 7
6 9
16
3
0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0
7 5
1 3
13 9
15
4
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0
13 3
1 7
0 5
17 9
16
4
1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
1 7
17 0
5 3
13 9
18
1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0

Note 1

The sample output is the .out file, which is the result you need to output. When $c=1$, you need to construct a valid scheme.

The sample answer is the .ans file, which only provides the answer for each test case and does not provide the construction scheme.

Constraints

For all data, it is guaranteed that $2 \le n \le 18$ and $1 \le T \le 3000$.

This problem is divided into subtasks, with a total of 20 test points. The specific distribution of test points can be seen in the table below. Columns like $(l, r)$ represent the number of test cases where $l \le n \le r$, and "No limit" means no additional restrictions. The meaning of $o$ will be noted later.

We organize the test points as follows:

• Subtask 1: $1 \sim 2$, $10\,\text{pts}$.
• Subtask 2: $3 \sim 4$, $10\,\text{pts}$.
• Subtask 3: $5 \sim 6$, $10\,\text{pts}$, depends on Subtasks 1, 2.
• Subtask 4: $7 \sim 8$, $10\,\text{pts}$, depends on Subtask 2.
• Subtask 5: $9 \sim 10$, $10\,\text{pts}$, depends on Subtasks 3, 4.
• Subtask 6: $11 \sim 12$, $10\,\text{pts}$, depends on Subtask 4.
• Subtask 7: $13$, $5\,\text{pts}$.
• Subtask 8: $14 \sim 16$, $15\,\text{pts}$.
• Subtask 9: $17 \sim 18$, $10\,\text{pts}$, depends on Subtasks 6, 7.
• Subtask 10: $19 \sim 20$, $10\,\text{pts}$, depends on Subtasks 5, 8, 9.

Each subtask is bundled for evaluation, and its score is the minimum score among all test points in that subtask. Subtask dependencies mean that a subtask will only be evaluated if all its dependent subtasks have non-zero scores, and the score percentage is also taken as the minimum of the dependent subtasks.

Special properties of $o$:

• $o=0$: No special properties guaranteed.
• $o=1$: Guaranteed $w=0$ in input.
• $o=2$: Guaranteed $w=2$ in input.
• $o=3$: Guaranteed $w=0$ or $w=1$ in input.
• $o=4$: Guaranteed $w=0$ or $w=2$ in input. (This special property has no separate partial points)

Impact of outputting the scheme on the answer:

• If $c=0$ is chosen, you will receive $80\%$ of the points for the test point if the answer is correct, otherwise $0$ points.
• If $c=1$ is chosen, you will receive full points for the test point if both the answer and the construction scheme are correct, otherwise $0$ points.

Therefore, if you are unsure about your construction scheme, carefully consider whether to output it.

Instructions for checker.cpp:

checker.cpp uses a command-line format similar to Testlib, but it is not based on Testlib, so no testlib.h file is required; it is also compatible with the Lemon format. Specifically, you can use it as follows:

Open a terminal, enter the directory containing checker.cpp, and first use the command g++ checker.cpp -o checker to generate the executable (requires a default C++11 or higher standard).

Assuming the input file is data.in, the output file is data.out, and the standard answer file is data.ans, place the executable checker and the data.in/out/ans files in the same directory, then execute the following command in the terminal:

• If using Windows, execute checker data.in data.out data.ans in cmd.
• If using Linux, execute ./checker data.in data.out data.ans in bash.

Wait a moment for the prompt information.

If you use Lemon for local evaluation, you can use the checker.cpp executable directly as the "Custom Validator" in Lemon.