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 are not invited.
50 points: The number of students n is small, no more than 512.
50 points: The number of students n is large, but is no more than 32768.
Input Format
The input contains only one test case. The first line contains two integers n and m, representing the number of students and the number of friends. In the following m lines, each line contains two IDs of students who are friends. The last line contains a sequence of student IDs who are planning the party.
The number of students n is no more than 32768.
Each student has no more than 256 friends.
Output format
Print the IDs of students (in increasing order) who are not invited.
Sample Input
6 5
1 0
0 4
2 0
1 4
0 5
1 3
Sample Output
2
5
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.
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 are not invited.
figure
Subtasks
Input Format
The input contains only one test case. The first line contains two integers n and m, representing the number of students and the number of friends. In the following m lines, each line contains two IDs of students who are friends. The last line contains a sequence of student IDs who are planning the party.
The number of students n is no more than 32768. Each student has no more than 256 friends.
Output format
Print the IDs of students (in increasing order) who are not invited.
Sample Input
Sample Output
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.