Problem Description

In a city, there is a group of children passionate about collecting cards.

Problem Description

Due to insufficient pocket money, they devised a method: pairing up, each contributing half of the money to buy two cards from a store. Subsequently, they race to the city center fountain, with the winner taking both cards. If both arrive simultaneously, each takes one card.

One day, all the children gathered together. They wanted to tally all the purchase records. However, their memories were vague, remembering only some of the purchases (and not knowing who got how many), and they counted their own cards. You need to write a program to help the children reconstruct a possible set of purchase records.

Input Format

The first line of input contains two integers $n, m$, representing the number of children and the number of remembered purchase records, respectively. The children are numbered from $1$ to $n$.

The second line contains $n$ integers, representing the number of cards each child has.

The next $m$ lines each contain two integers $a, b$, indicating that the children numbered $a$ and $b$ went together to buy cards.

Output Format

The first line of output contains an integer $k$, representing the total number of purchases.

The next $k$ lines each contain three integers. The first two integers are the numbers of the two children in a purchase. The third integer is the number of cards the first child won in this race ($0/1/2$).

The problem guarantees a solution. The total number of purchases is at most $1000$. If there are multiple purchase schemes, output any one. This problem uses a special judge.

Sample Input and Output

Sample Input #1

2 3
5 1
1 2
1 2
1 2

Sample Output #1

3
1 2 1
1 2 2
1 2 2

Sample Input #2

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

Sample Output #2

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

Sample Input #3

5 0
3 0 2 4 1

Sample Output #3

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

Notes

Data Size and Constraints

For $100\%$ of the data, it is guaranteed that $1 \le n \le 100$ and $0 \le m \le 1000$.

Notes

This problem is translated from COCI2008-2009 CONTEST #6 T6 SLICICE.

见题面 Input 部分

见题面 Output 部分