CF1876E.Ball-Stackable

With a problem title like that, there is no way this is going to be a graph problem.

Chaneka has a graph with $n$ vertices and $n-1$ edges. Some of the edges are directed and some of the edges are undirected. Edge $i$ connects vertex $u_i$ to vertex $v_i$. If $t_i=0$, edge $i$ is undirected. If $t_i=1$, edge $i$ is directed in the direction from $u_i$ to $v_i$. It is known that if you make all edges undirected, the graph becomes a tree$^\dagger$.

Chaneka wants to direct all undirected edges and colour each edge (different edges can have the same colour).

After doing that, suppose Chaneka starts a walk from an arbitrary vertex $x$ to an arbitrary vertex $y$ (it is possible that $x=y$) going through one or more edges. She is allowed to go through each edge either following the direction or opposite to the direction of the edge. She is also allowed to visit a vertex or an edge more than once. During the walk, Chaneka maintains a stack of balls that is initially empty before the walk. Each time Chaneka goes through an edge, she does the following:

• If Chaneka goes through it in the right direction, she puts a new ball with a colour that is the same as the edge's colour to the top of the stack.
• If Chaneka goes through it in the opposite direction, she removes the ball that is on the top of the stack.

A walk is stackable if and only if the stack is not empty before each time Chaneka goes through an edge in the opposite direction.

A walk is ball-stackable if and only if it is stackable and each time Chaneka goes through an edge in the opposite direction, the colour of the ball removed from the stack is the same as the colour of the edge traversed.

Is it possible to direct all undirected edges and colour each edge such that all stackable walks are also ball-stackable? If it is possible, find a construction example that uses the maximum number of different colours among all valid ways of directing and colouring. If there are multiple such solutions, output any of them.

$^\dagger$ A tree is a connected graph with no cycles.

题目名称如此，这绝不可能是一个图论问题。

Chaneka 有一个包含 $n$ 个顶点和 $n-1$ 条边的图。其中一些边是有向的，另一些是无向的。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。若 $t_i = 0$，则第 $i$ 条边为无向边；若 $t_i = 1$，则第 $i$ 条边为从 $u_i$ 指向 $v_i$ 的有向边。已知：若将所有边均视为无向边，则该图构成一棵树$^\dagger$。

Chaneka 希望将所有无向边定向，并为每条边染色（不同边可以染相同颜色）。

完成上述操作后，假设 Chaneka 从任意顶点 $x$ 出发，沿一条或多条边走到任意顶点 $y$（允许 $x = y$）。她可沿边的方向行走，也可逆着边的方向行走；也允许重复访问顶点或边。在行走过程中，Chaneka 维护一个初始为空的球栈。每次她经过一条边时，执行以下操作：

• 若她沿该边的正确方向经过，则将一个新球（其颜色与该边颜色相同）压入栈顶；
• 若她逆着该边的方向经过，则将栈顶的球弹出。

当且仅当每次 Chaneka 逆着边方向经过某条边前，栈均非空时，称该行走为栈可操作的（stackable）。

当且仅当该行走既是栈可操作的，且每次逆着边方向经过某条边时，所弹出的球的颜色均与该边颜色相同时，称该行走为球栈可操作的（ball-stackable）。

是否存在一种对所有无向边进行定向并为每条边染色的方案，使得所有栈可操作的行走也都是球栈可操作的？若存在，请构造一个满足条件的方案，且该方案所使用的不同颜色数目在所有合法定向与染色方案中达到最大。若存在多个这样的方案，输出任意一个即可。

$^\dagger$ 树是指连通且无环的图。

The first line contains a single integer $n$ ($2\leq n\leq10^5$) — the number of vertices in the graph.

The $i$-th of the next $n-1$ lines contains three integers $u_i$, $v_i$, and $t_i$ ($1 \leq u_i,v_i \leq n$; $0\leq t_i\leq1$) — an undirected edge connecting vectices $u_i$ and $v_i$ if $t_i=0$, or a directed edge from vertex $u_i$ to vertex $v_i$ if $t_i=1$. If you make all edges undirected, the graph becomes a tree.

第一行包含一个整数 $n$（$2\leq n\leq10^5$）—— 图中顶点的数量。

接下来的 $n-1$ 行中，第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $t_i$（$1 \leq u_i,v_i \leq n$；$0\leq t_i\leq1$）—— 若 $t_i=0$，则表示连接顶点 $u_i$ 和 $v_i$ 的一条无向边；若 $t_i=1$，则表示从顶点 $u_i$ 指向顶点 $v_i$ 的一条有向边。若将所有边均视为无向边，则该图成为一棵树。

A single line containing $-1$ if it is impossible.

Otherwise, the output consists of $n$ lines describing your construction. The first line contains an integer $z$ representing the number of different colours used. The $i$-th of the next $n-1$ lines contains three integers $p$, $q$, and $c$ ($1\leq p,q\leq n$; $1\leq c\leq z$) — the edge connecting vertices $p$ and $q$ in the graph is directed from vertex $p$ to vertex $q$ and is coloured with colour $c$. If there are multiple such solutions, output any of them.

Note that since there should be $z$ different colours in your construction, that means each colour from $1$ to $z$ must appear at least once in the graph.

如果无法实现，则输出一行包含 $-1$。

否则，输出由 $n$ 行组成，描述你的构造方案。第一行包含一个整数 $z$，表示所使用的不同颜色的数量。接下来的 $n-1$ 行中，第 $i$ 行包含三个整数 $p$、$q$ 和 $c$（$1\leq p,q\leq n$；$1\leq c\leq z$）—— 表示图中连接顶点 $p$ 和 $q$ 的有向边从顶点 $p$ 指向顶点 $q$，且该边的颜色为 $c$。若存在多个满足条件的解，输出任意一个即可。

注意：由于你的构造方案中应恰好使用 $z$ 种不同的颜色，因此颜色编号 $1$ 至 $z$ 必须在图中每种至少出现一次。

The following is the given graph.

Chaneka can direct all undirected edges and colour each edge as follows.

As an example, consider a stackable walk $3→1→5→2→5→4→5$. Let's show that that walk is ball-stackable.

1. Chaneka starts in vertex $3$. The stack is $[]$.
2. Chaneka moves to vertex $1$. She puts a ball of colour $3$. The stack is $[3]$.
3. Chaneka moves to vertex $5$. She puts a ball of colour $2$. The stack is $[3,2]$.
4. Chaneka moves to vertex $2$. She removes a ball of colour $2$ (same colour as the edge). The stack is $[3]$.
5. Chaneka moves to vertex $5$. She puts a ball of colour $2$. The stack is $[3,2]$.
6. Chaneka moves to vertex $4$. She puts a ball of colour $1$. The stack is $[3,2,1]$.
7. Chaneka moves to vertex $5$. She removes a ball of colour $1$ (same colour as the edge). The stack is $[3,2]$.

Since every time Chaneka removes a ball from the stack, it has the same colour as the edge traversed, then the walk above is ball-stackable. It can be shown that if we direct and colour the edges as shown above, any possible stackable walk is also ball-stackable.

以下是给定的图。

Chaneka 可以将所有无向边定向，并对每条边进行染色，如下所示。

例如，考虑一条可堆叠路径 $3→1→5→2→5→4→5$。我们来验证该路径是“球可堆叠”（ball-stackable）的。

1. Chaneka 起始于顶点 $3$，此时栈为 $[]$。
2. Chaneka 移动到顶点 $1$，放入一个颜色为 $3$ 的球，栈变为 $[3]$。
3. Chaneka 移动到顶点 $5$，放入一个颜色为 $2$ 的球，栈变为 $[3,2]$。
4. Chaneka 移动到顶点 $2$，移除一个颜色为 $2$ 的球（与所经边颜色相同），栈变为 $[3]$。
5. Chaneka 移动到顶点 $5$，放入一个颜色为 $2$ 的球，栈变为 $[3,2]$。
6. Chaneka 移动到顶点 $4$，放入一个颜色为 $1$ 的球，栈变为 $[3,2,1]$。
7. Chaneka 移动到顶点 $5$，移除一个颜色为 $1$ 的球（与所经边颜色相同），栈变为 $[3,2]$。

由于每次 Chaneka 从栈中移除球时，该球的颜色均与所经过边的颜色一致，因此上述路径是球可堆叠的。可以证明：若按上图所示方式对边进行定向和染色，则任意可能的可堆叠路径也必然是球可堆叠的。