문화 충돌

역사가들은 특정 발명이 어느 문화에서 어느 시점에 처음 생겨났는지에 흔히 관심을 가진다. 그러나 서로 다른 문화들이 때때로 만나 정보를 교환했기 때문에 이를 알아내기는 그리 쉽지 않다. 그러한 교류 중 어떤 것들이 일어났는지와 오늘날 어떤 문화들이 그 발명을 알고 있는지를 안다면, 때로는 그 발명이 어디에서 생겨났는지 알아낼 수 있다. 여러분은 바로 이 작업을 수행하는 프로그램을 작성해야 한다.

문화 간 만남에 관해 매우 단순화된 모델을 사용한다. $1$부터 $n$까지 번호가 매겨진 $n$개의 문화가 있으며, 특정 시점에 두 문화 사이에서 정보가 완전히 교환되는 경우를 제외하면 이들은 완전히 고립되어 살아간다고 가정한다. 이것이 평화로운 협력이었는지 전쟁을 통한 정복이었는지는 고려할 필요가 없다. 중요한 것은 만남 전에 한 문화가 그 발명을 알고 있었다면 만남 후에는 두 문화 모두 그 발명을 알게 된다는 점뿐이다. 문화의 수는 절대로 변하지 않는다는 점에 유의한다. 만남이 끝나면 두 문화는 다시 고립된 상태로 지내며, 다른 문화들과 서로 다른 방식으로 교류할 수 있다. 확실히 아는 유일한 사실은 만남 직후 이 두 문화가 정확히 동일한 지식을 지닌다는 것이다.

입력의 첫째 줄에 두 정수 $n$와 $k$가 주어지며, 여기서 $2 \le n \le 1\,000$이고 $1 \le k \le 10\,000$이다. $n$은 모델에 포함된 문화의 수이고, $k$은 고려하는 만남의 총횟수이다. 이어서 각각 두 정수 $a$와 $b$를 포함하는 $k$개의 줄이 주어지며, 두 정수 모두 $1...n$ 범위에 속한다. 각 줄은 $a$번 문화와 $b$번 문화 사이의 만남을 나타낸다. 만남은 주어진 순서와 정확히 같은 순서로 일어난다. 각 만남은 다음 만남이 일어나기 전에 완전히 끝난 것으로 가정한다.

만남에 대한 설명 뒤에는 오늘날 그 발명을 알고 있는 문화의 수인 정수 $2 \le m \le n$이 한 줄에 주어지고, 다음 줄에는 오늘날 그 발명을 알고 있는 문화들의 번호를 나타내는 $1...n$ 범위의 정수 $m$개가 주어진다.

프로그램은 $1...n$ 범위에 속하는 정수의 목록을 출력해야 한다. 각 수는 그 발명이 생겨났을 가능성이 있는 문화의 번호를 나타낸다. 더 정확히 말하면, 각 문화 $x$에 대해 그 발명이 생겨난 가능한 시점이 존재하여 오늘날 발명의 전파 상태가 주어진 것과 정확히 같아질 수 있다면 $x$를 목록에 포함하고, 그렇지 않으면 포함하지 않는다. 목록의 모든 수는 서로 달라야 하며 오름차순으로 정렬되어야 한다.