50086. Students and Party

I'm a slow walker, but I never walk backwards.

Write a program to find out people who are not "well-connected".

Task Description

We are given a set of $N$ students with ID from 0 to $N - 1$. and how they are friends of each. Note that we believe that friendship is mutual so if A is a friend of B, then B is a friend of A. We will be given a list of friendship, each of which has two student IDs indicating that these two students are friends of each other. Then we will be given the IDs of a group of students who are planning a party. This group of students will send invitation to all their friends. Please find out the IDs of all students who are not invited. For example, the following figure has 6 students and 5 pairs of friends. If 1 and 3 are planning for a party then only 2 and 5 is not invited.

p10175. Sample

Subtask

  • 50 points: The number of students $N$ is small.
  • 50 points: The number of students $N$ is large.

Input Format

The input contains only one test case. The first line contains two integers $N$ and $E$, representing the vertex number and the edge number of the social network graph. In the following $E$ lines, each line contains two Integers $vi$ and $vj$, which represent student IDs having a friendship. And the last line contains a sequence of student IDs who send invitation cards.

  • When $N$ is small, $N \leq 512.$
  • When $N$ is large, $N \leq 32768.$
  • Each student have no more than $k$ friends, $k \leq 256.$

Output Format

Print the ID of students in increasing order who are not invited.

Hint

In order to save time and space you cannot simply use a two dimensional array to store all friendship. Instead since everyone has at most $k$ friends, you can store the friends of each student separately. After knowing the friends of each student, you can go through all students in the party planning group, and mark the students who are going to the party in another array (using student ID as index). Any unmarked cell in that array indicates a student who is not invited.

Sample Input

6 5
1 0
0 4
2 0
1 4
0 5
1 3

Sample Output

2
5

Discussion