Problem: BigData Inc. is a corporation that has n data centers indexed from 1 to n that are located all over the world. These data centers provide storage for client data (you can figure out that client data is really big!).

Main feature of services offered by BigData Inc. is the access availability guarantee even under the circumstances of any data center having an outage. Such a guarantee is ensured by using the two-way replication. Two-way replication is such an approach for data storage that any piece of data is represented by two identical copies that are stored in two different data centers.

For each of m company clients, let us denote indices of two different data centers storing this client data as ci, 1 and ci, 2.

In order to keep data centers operational and safe, the software running on data center computers is being updated regularly. Release cycle of BigData Inc. is one day meaning that the new version of software is being deployed to the data center computers each day.

Data center software update is a non-trivial long process, that is why there is a special hour-long time frame that is dedicated for data center maintenance. During the maintenance period, data center computers are installing software updates, and thus they may be unavailable. Consider the day to be exactly h hours long. For each data center there is an integer uj (0 ≤ uj ≤ h - 1) defining the index of an hour of day, such that during this hour data center j is unavailable due to maintenance.

Summing up everything above, the condition uci, 1 ≠ uci, 2 should hold for each client, or otherwise his data may be unaccessible while data centers that store it are under maintenance.

Due to occasional timezone change in different cities all over the world, the maintenance time in some of the data centers may change by one hour sometimes. Company should be prepared for such situation, that is why they decided to conduct an experiment, choosing some non-empty subset of data centers, and shifting the maintenance time for them by an hour later (i.e. if uj = h - 1, then the new maintenance hour would become 0, otherwise it would become uj + 1). Nonetheless, such an experiment should not break the accessibility guarantees, meaning that data of any client should be still available during any hour of a day after the data center maintenance times are changed.

Such an experiment would provide useful insights, but changing update time is quite an expensive procedure, that is why the company asked you to find out the minimum number of data centers that have to be included in an experiment in order to keep the data accessibility guarantees.

Input

The first line of input contains three integers n, m and h (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000, 2 ≤ h ≤ 100 000), the number of company data centers, number of clients and the day length of day measured in hours. 

The second line of input contains n integers u1, u2, ..., un (0 ≤ uj < h), j-th of these numbers is an index of a maintenance hour for data center j. 

Each of the next m lines contains two integers ci, 1 and ci, 2 (1 ≤ ci, 1, ci, 2 ≤ n, ci, 1 ≠ ci, 2), defining the data center indices containing the data of client i.

It is guaranteed that the given maintenance schedule allows each client to access at least one copy of his data at any moment of day.

Output

In the first line print the minimum possible number of data centers k (1 ≤ k ≤ n) that have to be included in an experiment in order to keep the data available for any client.

In the second line print k distinct integers x1, x2, ..., xk (1 ≤ xi ≤ n), the indices of data centers whose maintenance time will be shifted by one hour later. Data center indices may be printed in any order.

If there are several possible answers, it is allowed to print any of them. It is guaranteed that at there is at least one valid choice of data centers.

Examples

Input

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


Output

1
3 

Input

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


Output

4
1 2 3 4 

Note

Consider the first sample test. The given answer is the only way to conduct an experiment involving the only data center. In such a scenario the third data center has a maintenance during the hour 1, and no two data centers storing the information of the same client have maintenance at the same hour.

On the other hand, for example, if we shift the maintenance time on hour later for the first data center, then the data of clients 1 and 3 will be unavailable during the hour 0.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.Iterator;
import java.io.IOException;
import java.io.Writer;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author palayutm
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        ProblemCDataCenterMaintenance solver = new ProblemCDataCenterMaintenance();
        solver.solve(1, in, out);
        out.close();
    }

    static class ProblemCDataCenterMaintenance {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt(), m = in.nextInt(), H = in.nextInt();
            Graph g = new Graph(n);
            int[] h = in.nextIntArray(n);
            for (int i = 0; i < m; i++) {
                int c1 = in.nextInt(), c2 = in.nextInt();
                if (h[c1 - 1] == (h[c2 - 1] + 1) % H) {
                    g.addEdge(c2 - 1, c1 - 1);
                }
                if (h[c2 - 1] == (h[c1 - 1] + 1) % H) {
                    g.addEdge(c1 - 1, c2 - 1);
                }
            }
            StronglyConnectedComponent scc = new Kosaraju(g);
            int[] outDegree = new int[scc.getComponentsNumber()];
            for (int i = 0; i < n; i++) {
                for (Edge edge : g.getEdges(i)) {
                    if (scc.getComponentID(i) != scc.getComponentID(edge.to)) {
                        outDegree[scc.getComponentID(i)]++;
                    }
                }
            }
            int[][] components = scc.getComponents();
            int p = -1, mi = n * 3;
            for (int i = 0; i < components.length; i++) {
                if (outDegree[i] == 0 && components[i].length < mi) {
                    mi = components[i].length;
                    p = i;
                }
            }
            out.println(components[p].length);
            for (int i = 0; i < components[p].length; i++) {
                out.print(components[p][i] + 1 + " ");
            }
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0;
        private int ptrbuf = 0;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int readByte() {
            if (lenbuf == -1) throw new UnknownError();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = stream.read(inbuf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

    }

    static class Edge {
        public int to;
        public long weight;

        public Edge(int to) {
            this.to = to;
        }

        public Edge(int to, long weight) {
            this(to);
            this.weight = weight;
        }

    }

    static class Graph {
        MyArrayList<Edge>[] g;

        public Graph(int n) {
            g = new MyArrayList[n];
            for (int i = 0; i < n; i++) {
                g[i] = new MyArrayList();
            }
        }

        public void addEdge(int from, int to) {
            g[from].add(new Edge(to));
        }

        public MyArrayList<Edge> getEdges(int from) {
            return g[from];
        }

        public int getVertexNumber() {
            return g.length;
        }

    }

    static interface StronglyConnectedComponent {
        int getComponentID(int vertexID);

        int getComponentsNumber();

        int[][] getComponents();

    }

    static class IntArrayList {
        private static final int DEFAULT_CAPACITY = 10;
        int[] array;
        int size;

        public IntArrayList() {
            this(DEFAULT_CAPACITY);
        }

        public IntArrayList(int capacity) {
            array = new int[capacity];
            size = 0;
        }

        public IntArrayList(int size, int initialValue) {
            String s;
            array = new int[size];
            Arrays.fill(array, initialValue);
            this.size = size;
        }

        public IntArrayList(int[] src) {
            array = Arrays.copyOf(src, src.length);
            size = array.length;
        }

        public void add(int value) {
            if (size == array.length) {
                enLarge();
            }
            array[size++] = value;
        }

        public int remove() {
            if (size == 0) {
                throw new NoSuchElementException();
            }
            return array[--size];
        }

        public int size() {
            return size;
        }

        public boolean isEmpty() {
            return size() == 0;
        }

        public int[] toArray() {
            return Arrays.copyOf(array, size);
        }

        private void enLarge() {
            int[] newArray = new int[(int) (array.length << 1)];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }

    }

    static class OutputWriter extends PrintWriter {
        public OutputWriter(OutputStream out) {
            super(out);
        }

        public OutputWriter(Writer out) {
            super(out);
        }

        public void close() {
            super.close();
        }

    }

    static class Kosaraju implements StronglyConnectedComponent {
        int[] belong;
        boolean[] used;
        int scc;
        int vertexNum;
        IntArrayList stack;

        public Kosaraju(Graph g) {
            vertexNum = g.getVertexNumber();
            belong = new int[vertexNum];
            used = new boolean[vertexNum];
            stack = new IntArrayList();
            for (int i = 0; i < vertexNum; i++) {
                if (!used[i]) dfs(g, i, -1);
            }
            Graph reverseGraph = new Graph(vertexNum);
            for (int i = 0; i < vertexNum; i++) {
                for (Edge e : g.getEdges(i)) {
                    reverseGraph.addEdge(e.to, i);
                }
            }
            Arrays.fill(used, false);
            while (!stack.isEmpty()) {
                int u = stack.remove();
                if (!used[u]) {
                    dfs(reverseGraph, u, scc++);
                }
            }
        }

        void dfs(Graph g, int u, int component_id) {
            used[u] = true;
            for (Edge e : g.getEdges(u)) {
                if (!used[e.to]) {
                    dfs(g, e.to, component_id);
                }
            }
            if (component_id == -1) stack.add(u);
            else belong[u] = component_id;
        }


        public int getComponentID(int vertexID) {
            return belong[vertexID];
        }


        public int getComponentsNumber() {
            return scc;
        }


        public int[][] getComponents() {
            int[][] ret = new int[scc][];
            IntArrayList[] components = new IntArrayList[scc];
            for (int i = 0; i < scc; i++) components[i] = new IntArrayList();
            for (int i = 0; i < vertexNum; i++) components[belong[i]].add(i);
            for (int i = 0; i < scc; i++) {
                ret[i] = components[i].toArray();
            }
            return ret;
        }

    }

    static class MyArrayList<T> implements Iterable<T> {
        private static final int DEFAULT_CAPACITY = 10;
        private static final double ENLARGE_SCALE = 2.0;
        Object[] array;
        int size;

        public MyArrayList() {
            this(DEFAULT_CAPACITY);
        }

        public MyArrayList(int capacity) {
            array = new Object[capacity];
            size = 0;
        }

        public void add(T value) {
            if (size == array.length) {
                enLarge();
            }
            array[size++] = value;
        }

        private void enLarge() {
            Object[] newArray = new Object[(int) (array.length * ENLARGE_SCALE)];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }


        public Iterator<T> iterator() {
            return new Iterator<T>() {
                private int currentIndex = 0;


                public boolean hasNext() {
                    return currentIndex < size;
                }


                public T next() {
                    return (T) array[currentIndex++];
                }
            };
        }

    }
}