물건 가져가기

국렬이는 신촌 어딘가에 있는 물건을 얻을 수 있는 사격장에 갔다. 사격장에 물품이 N개 있고, 각 물품에는 1부터 N까지 번호가 붙어 있다. 물품을 총으로 맞추면 그 물품을 가져갈 수 있다.

물건을 가져가는 데에는 제한이 있다. 각 물품마다 사전에 얻어야 하는 물품이 있고, 그 물품을 전부 얻어야 해당 물품을 가져갈 수 있다. 그렇지 않으면 해당 물품을 맞춰도 가져갈 수 없다. 예를 들어 A는 B와 C를 전부 얻어야 가져갈 수 있고, C는 D를 먼저 얻어야 가져갈 수 있다면, A를 가져가려면 B, C, D를 전부 얻은 뒤에 가져갈 수 있다.

쏘는 시점은 상관없다. 예를 들어 A는 B를 얻어야 가져갈 수 있고, B는 A를 얻어야 가져갈 수 있다면, B를 먼저 얻고 A를 가져가든 A를 먼저 얻고 B를 가져가든 상관없다. 즉, 이런 경우에는 둘 다 가져가지 않거나 둘 다 가져가야 한다.

각 물품을 얻었을 때 국렬이의 기분 변화 정도가 있다. 얻었을 때 역겨움과 혐오감이 몰려와서 기분이 낮아질 수도 있고, 반대로 환희감이 차올라서 기분이 높아질 수도 있다.

총알은 각 물품 개수만큼 있고, 국렬이는 사격의 마스터라 원하는 물건은 무조건 맞출 수 있다. 이때 국렬이가 얻을 수 있는 기분의 최대치를 이루는 물건들을 구하여라.

첫 줄에는 물품의 개수와 물품 간의 관계의 수를 나타내는 N과 M이 주어진다. (1 ≤ N ≤ 200, 1 ≤ M ≤ 400)

두 번째 줄부터 N + 1번째 줄까지는 각 물품을 얻었을 때 기분의 변화치 ti를 나타내는 정수가 주어진다. (−100,000 ≤ ti ≤ 100,000)

N + 2번째 줄부터 N + M + 1번째 줄까지 물품들 간의 관계에 대한 서로 다른 정수 2개 si, ei가 주어진다. si의 물품을 얻기 위해서는 ei를 얻어야 한다는 의미다. (1 ≤ si, ei ≤ N)

얻어야 하는 물품의 개수를 첫 줄에 출력하고, 다음 줄에 각 물품들의 번호를 공백으로 구분해 출력하라.

답이 여러 개인 경우에는 그 중 아무거나 출력하라.