CF260D Black and White Tree

题目描述

存在一棵 $n$ 个节点的树,树边有**非负整数**边权,每个节点都有颜色,且只可能是黑色或白色(用 $0$ 或 $1$ 表示)。原树不存在树边连接 $2$ 个同色的节点。 现给出每个节点的颜色和与这个节点相连的边的权值和,请您还原这棵树。

输入格式

第一行一个整数 $n$ $(2\le n\le10^5)$,表示节点数。 第 $2$ ~ $n+1$ 行,每行两个整数 $c_{i}$ , $s_{i}$ $(0\le c_i\le1,0\le s_i\le10^9)$ ,表示节点 $i$ 的颜色和与节点 $i$ 相连的边的权值和。

输出格式

共输出 $n-1$ 行,每行 $u,v,w$ ( 你需要保证 $1\le u,v\le n,0\le w\le10^9$ ),代表这条边的左右端点和权值。 如果存在多组解,输出任意一组即可。 输入数据保证至少存在一个符合要求的图。