Description

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.

Input Format

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 Format

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.

2 3
5 1
1 2
1 2
1 2

3
1 2 1
1 2 2
1 2 2

4 3
5 3 1 1
1 3
2 3
4 1

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

5 0
3 0 2 4 1

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

Hint

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 CONTEST #6 T6 SLICICE.

Translated by ChatGPT 5