Key Vertices Selection in Partitioned Graph

Given an undirected graph with $n$ vertices and $m$ edges that is divided into $k$ parts, where each part contains some vertices, your task is to select exactly one vertex from each part (called a key vertex) such that every edge has at least one endpoint that is a key vertex. In other words, if the key vertex chosen in the part containing vertex $u$ is not $u$ and the key vertex chosen in the part containing vertex $v$ is not $v$, then edge $(u,v)$ would not be covered. If a valid selection exists, output the key vertices for parts $1$ through $k$ (in order) as space‐separated integers; otherwise, output -1.


Input Format:
The first line contains three integers $n$, $m$, and $k$.
The second line contains $n$ integers, where the $i$-th integer indicates the part number (from 1 to $k$) to which vertex $i$ belongs.
Each of the next $m$ lines contains two integers $u$ and $v$ indicating an undirected edge between vertices $u$ and $v$.
Output Format:
If a valid selection exists, output $k$ integers (the key vertices for parts 1 through $k$, respectively) separated by single spaces; otherwise, output -1.

inputFormat

The first line contains three integers: n m k.

The second line contains n integers where the i-th integer (1-indexed) indicates the part number to which vertex i belongs (from 1 to k).

Then follow m lines, each containing two integers u and v (1-indexed) that denote an undirected edge between vertices u and v.

outputFormat

If there is a valid selection, output one line containing k space‐separated integers where the i-th integer is the key vertex chosen for part i. If no valid selection exists, output -1.

sample

4 3 2
1 1 2 2
1 3
2 4
3 4

2 3