← 返回题目列表

Codeforces · 1876/E

E. 可堆叠球

中文机器翻译题面 查看原题

有了这样的问题标题,这不可能是一个图形问题。

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 沿相反方向穿过边缘之前堆栈不为空时,步行才可堆叠。

步行是球可堆叠的当且仅当它是可堆叠的并且每次Chaneka穿过相反方向的边缘时,从堆叠中移除的球的颜色与穿过的边缘的颜色相同。

是否有可能引导所有无向边缘并为每个边缘着色,以便所有可堆叠行走也可堆叠球?如果可能的话,找到一个在所有有效的引导和着色方式中使用最大数量的不同颜色的构造示例。如果有多个这样的解,则输出其中任何一个。

$$$^\dagger$$$ 树是一个没有循环的连通图。

输入

第一行包含一个整数 $$$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$$$ 的有向边。如果将所有边设置为无向,则该图将变成一棵树。

输出

如果不可能,则包含 $$$-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$$$ 的每种颜色必须在图表中至少出现一次。

示例

输入 #1

5
2 5 1
1 3 0
5 4 0
1 5 1

输出 #1

3
1 5 2
5 4 1
2 5 2
3 1 3

注意

以下是给定的图表。

Chaneka 可以引导所有无向边并对每条边着色,如下所示。

作为一个例子,考虑一个可堆叠的步行$$$3→1→5→2→5→4→5$$$。让我们证明该步行是可堆叠的。

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 从堆叠中取出一个球时,它的颜色都与所经过的边缘相同,因此上面的行走是可堆叠球的。可以证明,如果我们如上所示对边缘进行定向和着色,则任何可能的可堆叠行走也是可堆叠的球。