ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU Team.GOV contest. Petrozavodsk training camp. Summer 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Last Season of Team.GOV

Time limit: 0.5 second
Memory limit: 64 MB
Four regional contests, twelve different teammates… Twenty sixth place is not that bad indeed, but World Finals would have been much better. And now the career is over, Team.GOV project is closed. The road back home to Yekaterinburg, graduation, and master's degree in France are ahead…
These thoughts were running around the head of Vadim Kantorov when the dean's voice drew him back to reality:
“Vadim, whom do you want to share a compartment with?”
A compartment on a sleeping car contains four main couchettes and two side couchettes. There are exactly 6n people in the Ural SU delegation, that's why the dean bought tickets for n consecutive compartments of a sleeping car. Every delegation member said what type of couchette they like more: main or side. Apart from that, everyone wants to share a compartment with their friends. The delegation needs to decide who occupies which compartment so that all these requirements are satisfied.


The first line contains an integer n (1 ≤ n ≤ 1000). The second line contains a bit string of length of 6n. i-th bit in this string is equal to 1 if the i-th delegation member wants to occupy a couchette of main type, and 0 if they want a couchette of side type. The next line contains an integer m that is the number of pairs of friends (0 ≤ m ≤ 15n). The next m lines contain all those pairs as integers aj and bj (1 ≤ aj < bj ≤ 6n). All these pairs are distinct.


Output n lines. Each line should contain a space-separated list of delegation members who should occupy a compartment together. Each pair of friends should occupy the same compartment. The order of people in a single list can be arbitrary. The order of lists also does not matter. If there are multiple solutions, you can output any of them. It is guaranteed that at least one solution exists.


1 2
7 8
1 2 3 4 5 6
7 8 9 10 11 12
Problem Author: Mikhail Rubinchik (idea by Dmitriy Kuznetsov)
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011
To submit the solution for this problem go to the Problem set: 1859. Last Season of Team.GOV