In the era of constructives and ad-hocs, what could be more sacrilegious than combining two query problems into one?

KOI City consists of $$$N$$$ intersections and $$$N - 1$$$ two-way roads. You can travel between two different intersections using only the given roads. In other words, the city's road network forms a tree structure. Roads are on a two-dimensional plane, and two roads do not intersect at locations other than the endpoints. Each road has an non-negative integer weight. This weight represents the time it takes to use the road.

KOI City was a small town until a few decades ago but began to expand rapidly as people arrived. In the midst of rapid expansion, the mayor had numbered the intersections between $$$1$$$ and $$$N$$$ for administrative convenience. The number system satisfies the following properties.

• Intersection 1 is the center of the city and is incident to at least 2 roads.
• The numbers assigned to intersections form one of the pre-orders of the tree rooted at intersection 1: for any subtree, the number of its root is the least number in that subtree.
• For each intersection, consider the lowest-numbered intersection among all adjacent (directly connected by road) intersections. When you list all adjacent intersections in a counterclockwise order starting from this intersection, the numbers go in increasing order.

With a large influx of people to KOI City, the traffic congestion problem has intensified. To solve this problem, the mayor connected the outermost cities with the outer ring road. Let $$$\{v_1, v_2, \ldots, v_k\}$$$ be the increasing sequence of numbers of all the intersections incident to exactly one road. For each $$$1 \le i \le k$$$, the mayor builds a two-way road between intersection $$$v_i$$$ and intersection $$$v_{(i \bmod k) + 1}$$$. The weight of each road is a nonnegative integer $$$w_i$$$. Due to the nature of the numbering system, you can observe that the outer ring road can be added in a two-dimensional plane in a way such that two roads do not intersect at any location except at the endpoint.

However, resolving traffic congestion only reduces commute times, making it easier for capitalists to exploit workers. Workers would not fall for the capitalists' disgusting plot — they want to go back to the good old days when they could apply heavy-light and centroid decomposition in KOI City! The workers successfully carried out the socialist revolution and overthrew the capitalist regime. Now they want to rebuild the structure of the existing KOI city by creating a new tree, which satisfies the following:

• Let $$$K$$$ be the number of vertices in the new tree; $$$K \le 4N$$$ should hold. From now on, we will label vertices of the new tree as $$$1, 2, \ldots, K$$$.
• For each vertex $$$i$$$ of the new tree, there is a corresponding set $$$X_i$$$ which is a subset of $$$\{1, 2, \ldots, N\}$$$.
• For all roads $$$(u, v)$$$ in the KOI City (both tree and outer ring roads), there exists a set $$$X_i$$$ where $$$\{u, v\} \subseteq X_i$$$.
• For all $$$1 \le j \le N$$$, let $$$S_j$$$ be the set of vertices $$$1 \le i \le K$$$ such that $$$j \in X_i$$$. Then $$$S_j$$$ must be non-empty, and should be a revolutionary set on the new tree.
• For all $$$1 \le i \le K$$$, it is true that $$$|X_i| \le 4$$$.

For a tree $$$T$$$ and a set $$$S$$$ which is a subset of vertices of $$$T$$$, the set $$$S$$$ is revolutionary on $$$T$$$ if for all vertices $$$u, v \in S$$$ it is connected under $$$S$$$. Two vertices $$$(u, v)$$$ are connected under $$$S$$$ if there exists a path in $$$T$$$ that only passes through the vertices in $$$S$$$.

For example, consider the following tree and the set $$$S = \{1, 2, 3, 4, 5, 6\}$$$.

In this case, $$$(1, 2)$$$, $$$(3, 5)$$$ and $$$(4, 6)$$$ are connected under $$$S$$$, while $$$(1, 6)$$$ and $$$(2, 7)$$$ are not connected under $$$S$$$.