Indian National Olympiad in Informatics

Online Programming Contest, 10-11 September, 2005


Advanced Division

Problem 2: An Odd Offer, (K Narayan Kumar, CMI)

The attendence at the Siruseri amusement park has been dropping and the park authorities have hit upon a new idea to boost attendence. A reward is offered to each visitor who can complete a "Odd Circuit" (explained below).

The amusement park consists of a number of rides which are connected by scenic walkways. These walkways are one-way roads. Each ride has been assigned a positive integer. Every visitor to the park is allowed to pick his starting ride. From this point, he is free to visit other rides using the walkways. He may visit any ride any number of times and may also use the walkways multiple times. At the end he must return back to the ride he started with. Otherwise he gets no reward. If he does return back to the ride he started with, then he calculates the smallest number amongst those assigned to the rides that he visited. If this number turns out to be a odd number then he is given a reward, otherwise not.

For example, suppose there are four rides at the Siruseri Amusement Park as described in the following figure:


Here, the numbers inside the circle identify the ride and the integer outside each circle is the number assigned to that ride.

A visitor can obtain the reward if he starts at ride 3 by just staying in ride 3. A visitor can also win the reward starting at ride 4 by visiting ride 3 and returning back to ride 4. You can check that there is no way to win the reward starting at any of the other rides.

Given a description of the rides at the Siruseri Amusement park, your task is to determine the set of rides from where a visitor can win the reward.

Input format

The first line of the input contains two integers N and M where N is the number of rides in the amusement park and M is the number of walkways. This is followed by M lines each containing two integers in the range 1, 2, ..., N. The two integers A and B on line i+1 (1 ≤ iM) indicate that the ith walkway goes from ride A to ride B. This is followed by N lines each containing a positive integer describing the numbers assigned to the rides. The integer on line M+i+1 (1 ≤ iN) is the number assigned to the ith ride. (Note that more than one ride may be assigned the same number.)

Output format

The first line of output contains a single integer K indicating the number of rides from where a visitor can start his trip and win a reward. This is followed by a line containing K integers listing out the rides from which the visitor can win the reward, in ascending order.

Test Data:

You may assume that 1 ≤ N ≤ 300 and 1 ≤ M ≤ 90000.


Here is the sample input and output corresponding to the example discussed above.

Sample Input

4 6
1 2 
2 3 
3 4
4 3 
4 2 
4 1

Sample Output

3 4

Copyright (c) IARCS 2003-2020;   Last Updated: 10 Nov 2005