← 返回题目列表

Codeforces · 260/D

D. 黑白树

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

棋盘上有一个绘制的树形图,由 n 个节点组成。让我们提醒您,如果无向图是连通的且不包含任何环,则该图称为树。

图表的每个节点都被涂成黑色或白色,以确保不存在通过边连接的两个颜色相同的节点。每条边都包含以非负整数形式写在其上的值。

一个坏孩子 Vasya 走到黑板上,在每个节点 v 附近写下数字 sv — 与该节点相关的所有边的值的总和。然后 Vasya 从棋盘上删除边缘及其值。

你的任务是通过节点颜色和数字 sv 恢复原始树。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 105) — 树中的节点数。接下来的 n 行包含空格分隔的整数对 ci、si (0 ≤ ci ≤ 1, 0 ≤ si ≤ 109),其中 ci 代表第 i 个顶点的颜色(0 代表白色,1 代表黑色),si 代表与绘制在棋盘上的树的第 i 个顶点相关的边的值之和。

输出

打印树形图的 n - 1 条边的描述。每个描述都是一组三个整数 vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 0 ≤ wi ≤ 109),其中 vi 和 ui — 是第 i 条边连接的节点的数量,wi 是其值。请注意,以下条件必须满足 cvi ≠ cui。

保证对于任何输入数据,至少存在一个满足这些数据的图。如果有多个解决方案,请打印其中任何一个。您可以按任何顺序打印边缘。打印数字时,用空格分隔它们。

示例

输入 #1

3
1 3
1 2
0 5

输出 #1

3 1 3
3 2 2

输入 #2

6
1 0
0 3
1 8
0 2
0 3
0 0

输出 #2

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