|Online Judge||Problem Set||Authors||Online Contests||User|
Blue and Red
The army is going to have a military exercise. The General has divided his men into two groups, Blue and Red. Just before the exercise, the General found out that M pairs of people are close friends. In his opinion, if two people from different groups are close friends, the training may be affected by the emotional factors. So here is your task. There are N soldiers in the army, who are numbered from 0 to N-1, find out the minimum number of soldiers to be eliminate so that there are no two people from different groups are close friends. You should output the numbers of the people eliminated in ascending order. If there more than one solution, output the lexicographically smallest one.
The first line of input is the number of test case.
The first line of test case contains two integers N and M.
The second line contains N integers.
The ith integer denote which group the ith soldier is in, 0 stands for blue, and 1 for red.
Then the M lines each contains two integers X and Y, denoted that X and Y are close friend.
(1 ≤ N ≤ 200 , 0 ≤ M ≤ 20000).
There is a blank line before each test case.
For each test case output the answer on a single line, which contains the minimum number of the soldiers to be eliminated followed by the sequence of their numbers.
4 2 1 0 1 0 1 2 2 0 1 0 1 1 0 2 2 0 1 0 1 1 1 3 2 0 0 1 0 1 1 2
1 0 1 0 1 0 1 1
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator