Slicice

수영장이 터진 뒤, Mirko와 Slavko는 카드를 모으기 시작했다. 이들의 동네에서는 카드 수집을 진지하게 여겨서, 카드의 구매와 교환에 엄격한 규칙이 있다.
카드 구매는 항상 두 아이가 함께 한다. 각자 필요한 금액의 절반씩을 내고 카드 두 장을 산다. 그런 다음 시내 분수까지 달리기 경주를 해서 이긴 아이가 두 장을 모두 가진다. 정확히 동시에 도착하면 각자 한 장씩 가진다.
처음에는 규칙이 잘 지켜지는 듯했지만, 곧 일부 아이들이 이런 구매만으로는 가질 수 없는 카드를 갖고 있다는 의혹이 제기되기 시작했다.
어느 날 모든 아이들이 모여 부정이 있었는지 확인하기로 했다. 아이들은 각자 현재 갖고 있는 카드의 정확한 개수에 대해서는 합의할 수 있었다. 또한 누가 누구와 함께 가게에 갔는지에 대한 부분적인 목록도 만들었지만, 각 경주에서 누가 이겨서 카드를 가져갔는지는 알지 못한다.
모든 구매에 누가 참여했고 그 뒤의 경주에서 누가 이겼는지를 결정하여, 모든 구매가 끝난 뒤의 카드 개수가 주어진 개수와 일치하도록 하는 프로그램을 작성하시오.
구매가 시작되기 전에는 아이들이 카드를 한 장도 갖고 있지 않았다고 가정한다.
가능한 해가 여러 개라면 아무거나 하나 출력한다.

첫째 줄에 정수 \(N\)과 \(M\) (\(1 \le N \le 100\), \(0 \le M \le 1000\))이 주어진다. 아이의 수와 아이들이 기억하는 구매의 횟수이다. 아이들에게는 \(1\)부터 \(N\)까지 번호가 붙어 있다.

둘째 줄에 \(N\)개의 정수가 주어진다. 각 아이가 현재 갖고 있는 카드의 개수이다.

다음 \(M\)개의 줄에는 각각 두 정수가 주어진다. 해당 구매를 한 두 아이의 번호이다.

첫째 줄에 전체 구매 횟수를 출력한다.

다음 각 줄에는 구매를 하나씩 설명한다. 구매의 설명은 세 수로 이루어진다: 구매를 한 두 아이의 번호와, 경주 후 첫 번째 아이가 받은 카드의 개수인 \(0\), \(1\) 또는 \(2\)이다.

참고: 해는 항상 존재하지만 유일하지 않을 수 있다. 전체 구매 횟수는 최대 \(1000\)이다.

riseoj 작성

출처 COCI 2008/2009 Contest 6