Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Blue and Red
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 3987Accepted: 1059


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.

Sample Input


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


[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