19579번 - 물건 가져가기 스페셜 저지

국렬이는 신촌 어딘가에 있는 물건을 얻을 수 있는 사격장에 갔다. 해당 사격장에 물품이 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번째 줄까지는 각 물품을 얻었을 때 기분의 변화치 t_i를 나타내는 정수가 주어진다. (−100,000 ≤ t_i ≤ 100,000)

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

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

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