Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Blue and Red
Description 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. Input 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 i^{th} integer denote which group the i^{th} 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. Output 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. Sample Input 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 Sample Output 1 0 1 0 1 0 1 1 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator