310725: CF1876E. Ball-Stackable

E. Ball-Stackabletime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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.

ExampleInput

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

Output

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

Note

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.

题目大意：

题目描述了一个图论问题，给定一个有 n 个顶点和 n-1 条边的图，其中一些边是有向的，一些边是无向的。每条边连接两个顶点，如果边的类型为 0，则表示该边是无向的；如果为 1，则表示该边是有向的。已知如果将所有边都看作无向的，那么这个图将变成一棵树。

题目要求我们将所有无向边赋予方向，并为每条边着色。着色后，从一个顶点 x 出发，通过一条或多条边到达另一个顶点 y（x 和 y 可以相同）。在行走过程中，可以沿着边的方向或者逆着边的方向行走，并且可以多次访问顶点或边。在行走过程中，维护一个球的堆栈，初始时为空。每当通过一条边时，如果沿着边的方向行走，就在堆栈顶部放置一个与边同色的球；如果逆着边的方向行走，则从堆栈顶部移除一个球。

如果在一个行走过程中，每次逆着边方向行走前，堆栈都不为空，则称该行走是“可堆叠的”。如果行走是可堆叠的，并且在每次逆着边方向行走时，从堆栈移除的球的颜色的与边的颜色相同，则称该行走是“可球堆叠的”。

问题是：是否可以给所有无向边赋予方向并着色，使得所有可堆叠的行走也是可球堆叠的。如果可以，给出一种着色方案，使得使用的不同颜色的数量在所有有效的方案中最大。如果有多种这样的方案，输出其中任意一种。

输入输出数据格式：

输入：
- 第一行包含一个整数 n（2≤n≤10^5），表示顶点的数量。
- 接下来的 n-1 行，每行包含三个整数 u_i, v_i 和 t_i（1≤u_i,v_i≤n；0≤t_i≤1），表示一条边。如果 t_i 为 0，则表示边是无向的；如果为 1，则表示边是有向的。

输出：
- 如果不可能实现题目要求，输出一行包含 -1。
- 如果可以，第一行输出一个整数 z，表示使用的不同颜色的数量。
- 接下来的 n-1 行，每行输出三个整数 p, q 和 c（1≤p,q≤n；1≤c≤z），表示从顶点 p 到顶点 q 的边是有向的，并且颜色为 c。如果有多种方案，输出其中任意一种。

注意，由于构造中应该有 z 种不同的颜色，这意味着从 1 到 z 的每种颜色必须在图中至少出现一次。题目大意： 题目描述了一个图论问题，给定一个有 n 个顶点和 n-1 条边的图，其中一些边是有向的，一些边是无向的。每条边连接两个顶点，如果边的类型为 0，则表示该边是无向的；如果为 1，则表示该边是有向的。已知如果将所有边都看作无向的，那么这个图将变成一棵树。 题目要求我们将所有无向边赋予方向，并为每条边着色。着色后，从一个顶点 x 出发，通过一条或多条边到达另一个顶点 y（x 和 y 可以相同）。在行走过程中，可以沿着边的方向或者逆着边的方向行走，并且可以多次访问顶点或边。在行走过程中，维护一个球的堆栈，初始时为空。每当通过一条边时，如果沿着边的方向行走，就在堆栈顶部放置一个与边同色的球；如果逆着边的方向行走，则从堆栈顶部移除一个球。 如果在一个行走过程中，每次逆着边方向行走前，堆栈都不为空，则称该行走是“可堆叠的”。如果行走是可堆叠的，并且在每次逆着边方向行走时，从堆栈移除的球的颜色的与边的颜色相同，则称该行走是“可球堆叠的”。 问题是：是否可以给所有无向边赋予方向并着色，使得所有可堆叠的行走也是可球堆叠的。如果可以，给出一种着色方案，使得使用的不同颜色的数量在所有有效的方案中最大。如果有多种这样的方案，输出其中任意一种。 输入输出数据格式： 输入： - 第一行包含一个整数 n（2≤n≤10^5），表示顶点的数量。 - 接下来的 n-1 行，每行包含三个整数 u_i, v_i 和 t_i（1≤u_i,v_i≤n；0≤t_i≤1），表示一条边。如果 t_i 为 0，则表示边是无向的；如果为 1，则表示边是有向的。 输出： - 如果不可能实现题目要求，输出一行包含 -1。 - 如果可以，第一行输出一个整数 z，表示使用的不同颜色的数量。 - 接下来的 n-1 行，每行输出三个整数 p, q 和 c（1≤p,q≤n；1≤c≤z），表示从顶点 p 到顶点 q 的边是有向的，并且颜色为 c。如果有多种方案，输出其中任意一种。 注意，由于构造中应该有 z 种不同的颜色，这意味着从 1 到 z 的每种颜色必须在图中至少出现一次。