TastyFriedPussy:
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

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

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

airsaylongcome:
Lol! Nice one @GreatIgboman. Something was so damn off with a younging rushing out with a solution. And sound so in C++.

Valid points though about the need to have more posts and engagements about DSA. Not just talking about it , but more hardcore stuff.

Anyway for me TastyFriedWhatever is the same person as sqlPAIN.

airsaylongcome:
Lol! Nice one @GreatIgboman. Something was so damn off with a younging rushing out with a solution. And sound so in C++.

Valid points though about the need to have more posts and engagements about DSA. Not just talking about it , but more hardcore stuff.

Anyway for me TastyFriedWhatever is the same person as sqlPAIN.

GREATIGBOMAN:
sqlPAIN

I dare u to explain your solution line by line.


chances are, u don't even understand what you've pasted.

GREATIGBOMAN:
sqlPAIN

I dare u to explain your solution line by line.


chances are, u don't even understand what you've pasted.

sqlPAIN:

Even if I did, you'd not be smart enough to understand....so stick to react JS and co

GREATIGBOMAN:



U can't, because there no place online to copy the explanation.

I'm very sure you're not older than 20years of age

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

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...

sqlPAIN:
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.....

SavageBoy:
Fact: Nobody get mouth like Greatigboman for here. The guy just dey give me joy

When I saw the rubbish post, I just knew it was that tasty-fried-idiot. Like what someone once told him here, na yahoo you go later use your Laptop do.

spartan117:
Lol this thread is pure comedy GREATIGBOMAN be calming down small

sqlpain aka tastyfried hope you have learnt your lesson?
Go and sin no more

airsaylongcome:


Na still GIM tell am say na yahoo hin go use that laptop do las las

SavageBoy:


Lol. With this his toxic and negative attitude, even if he abandons programming for yahoo, he wont still succeed.

He's busy calling out people that are doing better than him. None of the persons he called out has ever blamed or cursed their father.

Do you even expect someone that can call out his father in a public forum like this to be sensible and successful in life?

He claim he is not doing programming for the money, yet he's creating a thread on how demotivating learning programming can be without money.

Tastyfried idiot or whatever they call you. Programming is not for you. Better sell that your laptop and use the money to search for a solution to your problem.

niel63:
I am a Web Dev who likes React, Vue, Svelte and those small small UI toolkits that makes web dev look like telling a story. And you know what, I like am die.

I am in agreement that I know nothing but I hope you know its just a matter of me deciding to pick pick up another language if I feel the need to... as I am currently trying to choose between golang and rust right now

And I promise to drop all these in a heartbeat the moment I find something even more lucrative and enriching than this... you know why? Na money I dey find.

If you like wipe head for wall like 55 times, e no go still change the fact say everything dey for us to learn.

I am no pro programmer doing some tricky DSA stuffs like that small 12years old boy wey like to talk about IBM Watson and AI like say na him papa do am.

Being happy is a gift and you choose your path. Some people do not know basic html structure and they are in tech making big money.

So, tech isn't about being bitter about others... rather, it's about solving problems in real life even if it's just creating a shopping cart.

You're so good, yet you let someone else create ChatGPT. You're a mumu boy!!!

class Node:
  def __init__(self, id, col, val):
    self.id = id
    self.color = col
    self.value = val
    
  def __str__(self):
    return f"id: {self.id}, color: {self.color}, value: {self.value}"
    
    
class Result:
  def __init__(self, n1, n2, w):
    self.startnode = n1
    self.endnode = n2
    self.weight = w
    
  def __str__(self):
    return f"sn: {self.startnode.id}, en: {self.endnode.id}, weight: {self.weight}"
    

def read_inputs():
  n = int(input())
  res = set()
  for i in range(1, n + 1):
    s = input().split()
    res.add(Node(i, int(s[0]), int(s[1])))
  return res
  
def solve(nodes):
  res = []
  while len(nodes) != 0:
    maxn = max(nodes, key=lambda v: v.value)
    # check stray nodes
    if maxn.value == 0:
      resolve_res = [next_valid_node(maxn, res)]
    else:
      resolve_res = resolve_edges(maxn, nodes) 
    nodes.remove(maxn)  
    res.extend(resolve_res)
  return res
    
def resolve_edges(maxn, nodes):     
  res = []
  while True:
    minn = pick_min(maxn, nodes)
    if minn is None:
      break
    if maxn.value >= minn.value:
      res.append(Result(maxn, minn, minn.value))
      maxn.value -= minn.value
      nodes.remove(minn)
    else:
      res.append(Result(maxn, minn, maxn.value))
      minn.value -= maxn.value
      nodes.add(maxn)
      break
  return res
    
def pick_min(maxn, nodes):
  minn = Node(-1, -1, 999)
  for node in nodes:
    # check colors, reject same color nodes
    if node.color == maxn.color:
      continue
    if node.value < minn.value:
      minn = node
  return minn if minn.value != 999 else None
  
def next_valid_node(strayn, nodes):
  straycol = strayn.color
  for node in nodes:
    startcol, endcol = node.startnode.color, node.endnode.color
    if startcol != straycol:
      return Result(strayn, node.startnode, strayn.value)
    if endcol != straycol:
      return Result(strayn, node.startnode, strayn.value)

def main():
  nodes = read_inputs()
  nodes_test = {
    Node(1,1,0),Node(2,0,3),Node(3,1,8 ),
    Node(4,0,2),Node(5,0,3),Node(6,0,0)
  }
  nodes_test2 = {
    Node(1,1,3),Node(2,1,2),Node(3,0,5)
  }
  res = solve(nodes)
  [print(r.startnode.id, r.endnode.id, r.weight) for r in res]

if __name__ == "__main__":
  main()

res = solve(nodes)

namikaze:
The approach is;
pick the node with the max sv value, either white or black, and then distribute value (by substracting from the sv) to the smallest nodes of the opposite color untill sv becomes zero or the smallest opposite color node is bigger, then repeat with the next max sv node, nodes visited are not reused. this should work for valid inputs