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
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 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