A board has got a painted tree graph, consisting of n nodes. Let us remind you that a non-directed graph is called a tree if it is connected and doesn't contain any cycles.

Each node of the graph is painted black or white in such a manner that there aren't two nodes of the same color, connected by an edge. Each edge contains its value written on it as a non-negative integer.

A bad boy Vasya came up to the board and wrote number sv near each node v — the sum of values of all edges that are incident to this node. Then Vasya removed the edges and their values from the board.

Your task is to restore the original tree by the node colors and numbers sv.

Input
The first line of the input contains a single integer n (2 ≤ n ≤ 105) — the number of nodes in the tree. Next n lines contain pairs of space-separated integers ci, si (0 ≤ ci ≤ 1, 0 ≤ si ≤ 109), where ci stands for the color of the i-th vertex (0 is for white, 1 is for black), and si represents the sum of values of the edges that are incident to the i-th vertex of the tree that is painted on the board.

Output
Print the description of n - 1 edges of the tree graph. Each description is a group of three integers vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 0 ≤ wi ≤ 109), where vi and ui — are the numbers of the nodes that are connected by the i-th edge, and wi is its value. Note that the following condition must fulfill cvi ≠ cui.

It is guaranteed that for any input data there exists at least one graph that meets these data. If there are multiple solutions, print any of them. You are allowed to print the edges in any order. As you print the numbers, separate them with spaces.


Sample input
3
1 3
1 2
0 5
Sample output

3 1 3
3 2 2

Sample input
6
1 0
0 3
1 8
0 2
0 3
0 0

Sample output
2 3 3
5 3 3
4 3 2
1 6 0
2 1 0

.

That shit is difficult.. next question please !!!

Dahyur119:
That shit is difficult.. next question please !!!

how is it difficult?

Bc I can’t solve it

.

sqlPAIN:
As usual, I expect threads like this to be deserted on this section because most of the folks here are nothing but ordinary web developers.... All those one's that answer "guru" on this section are nowhere to be found @tensazangetsu20(come a use your hash map or quick sort) @qtguru @Sleekcode @namikaze @GREATIGBOMAN @mocochannel (most especially you), @Deicide @Ayinke93 @Alphabyte why are yall no where to be found......I'll be dropping a solution in a minute, give me a sec or two...SMH

Mr google developer please solve it let others learn. No need bringing others down. You guys in this section are so proud for people still learning hello world. Don't worry time will teach you all great lessons. Even the greatest competitive programmers aren't as condescending as a lot of you act on this section.

tensazangetsu20:


Mr google developer please solve it let others learn. No need bringing others down. You guys in this section are so proud for people still learning hello world. Don't worry time will teach you all great lessons. Even the greatest competitive programmers aren't as condescending as a lot of you act on this section.

mehn shut ur trap and go and sit down... You can't solve it be say you can solve it, rubbish. this is light years out of your league, you're not a real programmer, your just an ordinary web dev,period!!!so Bleep of and go continue with react,vue, CSS and the likes.... Learning hello world? Lolzzz

sqlPAIN:
mehn shut ur trap and go and sit down... You can't solve it be say you can solve it, rubbish. this is light years out of your league, you're not a real programmer, your just an ordinary web dev,period!!!so Bleep of and go continue with react,vue, CSS and the likes.... Learning hello world? Lolzzz

.

Some pple need to learn manners. The sky is wide for you all to fly without bumping each other. Why mention names, why don't you simply look front.

some people are just pouring out their frustrations

//Author- sqlPAIN
//C++
#include <bits/stdc++.h>
using namespace std;

typedef long long int64;
#define endl &#39;\n&#39;
#define SZ(c) ((int)(c).size())
#define ALL(c) (c).begin(), (c).end()
#define REP(I, n) for (int I = 0; I<(int)n; ++i)
const int
MAXN = 1 << 17;
int N;

multiset< pair<int, int >> S[2];
int data[MAXN];

int find (int x)
{
return (data[x] < 0) ? X : data[X] = find(data[X]);
}
int getSize(int x)
{
return -data[ find(X) ];
}
void unlite(int u, int v)
{
u=find(u);
v=find(v);
if (u==v) return;
if (getSize(u) < getSize(v))
swap(u,v);
data[u] +=data[v];
data[v] = u;
}
strict edge
{
int u,v,w;
};
vector<edge> edges;
int color [MAXN];
int main()
{
ios::sync_with_stdio(0);
member(data, -1, sizeof(data));
cin>> N;
REP(i, N)
{

int c, w;
cin>>c>>w;

color[i] =c;

if (w>0)
S[c].insert(make_pair(w,i));

}

while (!S[0].empty() && !S[1].empty())
{
auto w0 = *S[0].begin(); S[0].erase(S[0].begin());
auto w1 = *S[1].begin(); S[1].erase(S[1].begin());

int edgeCost = min(w0.first, w1.first);
edges.push_back((edge){w0.second, w1.second, edgeCost});

unite(w0.second, w1.second);

w0.first -= edgeCost;
w1.first -= edgeCost;

if (w0.first > 0) S[0].insert(w0);
if (w1.first > 0) S[1].insert(w1);
}

REP(i, N) if (i > 0)
if (color[i] != color[0] && find(i) != find(0))
{
unite(i, 0);
edges.push_back((edge){0, i, 0});
}
REP(i, N) if (color[i] != color[0] && find(i) == find(0))
{
REP(j, N) if (color[j] != color[i] && find(i) != find(j))
{
unite(i, j);
edges.push_back((edge){i, j, 0});
}
break;
}
for (auto e : edges)
cout << e.u + 1 << " " << e.v + 1 << " " << e.w << endl;
return 0;
}

sqlPAIN:
As usual, I expect threads like this to be deserted on this section because most of the folks here are nothing but ordinary web developers.... All those one's that answer "guru" on this section are nowhere to be found @tensazangetsu20(come a use your hash map or quick sort) @qtguru @Sleekcode @namikaze @GREATIGBOMAN @mocochannel (most especially you), @Deicide @Ayinke93 @Alphabyte why are yall no where to be found......I'll be dropping a solution in a minute, give me a sec or two...SMH

Because I'm waiting to copy your solution, jokes aside I haven't studied my DSA so I can't be as strong as you guys.

sqlPAIN:
mehn shut ur trap and go and sit down... You can't solve it be say you can solve it, rubbish. this is light years out of your league, you're not a real programmer, your just an ordinary web dev,period!!!so Bleep of and go continue with react,vue, CSS and the likes.... Learning hello world? Lolzzz

I really hope you're making a lot of money, TBH.

Kaycee54321:


I really hope you're making a lot of money, TBH.

Haba to be fair, that's a wrong mindset Algo and DSA is key, not just money, I don't get why sqlPain is angry, we've never claimed to be the champion in dev.

Kaycee54321:


I really hope you're making a lot of money, TBH.

I don't care about money, money is not my problem. My father is wealthy, I am wealthy too. Unlike most of you mere web developers, my interest in coding was not because of money...

qtguru:


Haba to be fair, that's a wrong mindset Algo and DSA is key, not just money, I don't get why sqlPain is angry, we've never claimed to be the champion in dev.

I'm just saying 'cause of the nature of his outbursts.
A bloke that keeps saying stuff like 'you're just a mere web developer' to strangers online should at least, have some financial muscle to back up the unnecessary conceit...

I don't know why I never see stuff like this on Quora or Discord...just among my fellow black brethren...

sqlPAIN:
I don't care about money, money is not my problem. My father is wealthy, I am wealthy too. Unlike most of you mere web developers, my interest in coding was not because of money...

LOL.

K.

Kaycee54321:


I'm just saying 'cause of the nature of his outbursts.
A bloke that keeps saying stuff like 'you're just a mere web developer' to strangers online should at least, have some financial muscle to back up the unnecessary conceit...

I don't know why I never see stuff like this on Quora or Discord...just among my fellow black brethren...

Well to each their own, I'm not in that school of trashing people for knowledge or lack of. Everybody has their opinions.

But we should have some Algo and DSA posts on NL. That's a valid point though, TastyFriedPussy has been consistent with codeforce.

Rubbish....... Simple tree problem they can't solve...If it's to be talking about react, vue,svelte, front-end and back-end,flex box,grid, django and all those fancy rubbishes, that's where you'll see all of them, claiming "tech guru's in the house"..Rubbish. But when it's time for real sh*t, they'll all vanish.. Ordinary websites all of you are developing, small thing you're shouting I'm In tech, I'm in tech. What tech. You think web dev is technology? Rubbish.....

I can't just wait for when chatGpt would get creative enough to start weeding you all out.
Nonsense

Omo, if you give this guy a job to teach computer science in secondary school, e fit use laptop charger spoil person pikin head.

TBH, I like the info sharing among guys in dev on NL.

For data guys, na just ONE active thread...and even there sef, interaction na bare minimum.

sqlPAIN:

while (!S[0].empty() && !S[1].empty())
{
auto w0 = *S[0].begin(); S[0].erase(S[0].begin());
auto w1 = *S[1].begin(); S[1].erase(S[1].begin());

int edgeCost = min(w0.first, w1.first);
edges.push_back((edge){w0.second, w1.second, edgeCost});

unite(w0.second, w1.second);

w0.first -= edgeCost;
w1.first -= edgeCost;

if (w0.first > 0) S[0].insert(w0);
if (w1.first > 0) S[1].insert(w1);
}

REP(i, N) if (i > 0)
if (color[i] != color[0] && find(i) != find(0))
{
unite(i, 0);
edges.push_back((edge){0, i, 0});
}
REP(i, N) if (color[i] != color[0] && find(i) == find(0))
{
REP(j, N) if (color[j] != color[i] && find(i) != find(j))
{
unite(i, j);
edges.push_back((edge){i, j, 0});
}
break;
}
for (auto e : edges)
cout << e.u + 1 << " " << e.v + 1 << " " << e.w << endl;
return 0;
}

As usual.


Screaming out of your lungs when your solution is copied word for word.
This your solution have been committed before 7 years ago.

Unless you're same person who committed it, You need to go back and hide in your cave sir.

Post your own solution with different method from those on the internet.

Don't post copied solutions.

Even if u copy a solution from darkweb I'll catch u

https://github.com/mukel/ProgrammingContests/blob/master/Codeforces/260/D%5B%20Black%20and%20White%20Tree%20%5D.cpp

Na wa however even if it is a copy, I must admit that there are some valid points. ChatGPT will take over some web dev like site-building and simple code structure.

We should encourage more Algorithms and DSA, and other parts. With joint effort i don't think that will be an issue, my only gripe is why the insults

Can't we all decide to improve Algo/DSA knowledge collectively?

I used to do Algo/DSA in Java, C++ was hard to Algo for me, but i think we can do it collectively, One Data Structure at a time.

What say ?

.

sqlPAIN:
While you were busy learning HTML, I was learning how to copy solutions, while you were busy learning CSS, I was learning how to copy solutions , while you were busy learning JavaScript, I was learning how to copy even more solutions, while you were busy learning react, I was learning discrete solutions copy techniques , while you were busy learning python, I was learning Learn Data structures and solutions copy algorithms (still learning), while you were busy learning django, I was learning algorithms(still learning)..... Rubbish

U were busy learning how to copy solutions

GREATIGBOMAN:



Pigs as usual.


Screaming out of your lungs when your solution is copied word for word.
This your solution have been committed before 7 years ago.

Unless you're same person who committed it, You need to go back and hide in your cave sir.

https://github.com/mukel/ProgrammingContests/blob/master/Codeforces/260/D%5B%20Black%20and%20White%20Tree%20%5D.cpp

exactly......rubbish

sqlPAIN:
exactly......rubbish
While u expose me na?

.

Rubbish.... Everything is not front-end and back-end......
..

qtguru:
Na wa however even if it is a copy, I must admit that there are some valid points. ChatGPT will take over some web dev like site-building and simple code structure.

We should encourage more Algorithms and DSA, and other parts. With joint effort i don't think that will be an issue, my only gripe is why the insults

Can't we all decide to improve Algo/DSA knowledge collectively?

I used to do Algo/DSA in Java, C++ was hard to Algo for me, but i think we can do it collectively, One Data Structure at a time.

What say ?

DSA has been encouraged. Besides learning DSA to pass programming interviews and doing competitive programming are two separate things entirely. I looked up the solution from GREATIGBOMAN and apparently, the question uses a black-white tree data structure a very advanced data structure that will never come up in any interview. It's not even taught in undergraduate computer science curriculum.

What will come up in interviews are things you see on leetcode that the dude was condescending about. Hashmaps, sorting, and graph traversal questions using bfs and df alongside other data structures. As long as you can solve medium questions using these basic data structures you can crack any faang interview provided you are given the opportunity. The keyword is solve o not copy from github