P6472 [COCI 2008/2009 #6] SLICICE

In a city, there is a group of kids who love collecting cards.

Because their pocket money is not enough, they came up with an idea: they form pairs, each person pays half the money, and they go to the store to buy two cards. Then they race to the fountain in the city center. The winner gets both cards. If they arrive at the same time, each takes one card. One day, all the kids gathered together. They wanted to list all purchase records. However, their memories were a bit unclear: they only remembered part of the purchase records (and they do not know who got how many cards), but they did count how many cards each of them has. You need to write a program to help them reconstruct one possible set of purchase records.

The first line contains two integers $n, m$, representing the number of kids and the number of purchase records they still remember. Kids are numbered from $1$ to $n$. The second line contains $n$ integers, where the $i$-th integer is the number of cards owned by kid $i$. The next $m$ lines each contain two integers $a, b$, meaning that kids $a$ and $b$ went to buy cards together once.

Output the first line with an integer $k$, the total number of purchases. In the next $k$ lines, output three integers per line. The first two integers are the indices of the two kids in that purchase. The third integer is the number of cards won by the first kid in that race ($0/1/2$). **It is guaranteed that a solution exists. The total number of purchases is at most $1000$. If there are multiple valid solutions, output any one. This problem uses SPJ.**

#### Constraints For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 100$, $0 \le m \le 1000$. #### Notes **This problem is translated from [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #6](https://hsin.hr/coci/archive/2008_2009/contest6_tasks.pdf) *T6 SLICICE*.** Translated by ChatGPT 5