| Author: | A. Baranov | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
Young programmer Vasya is engaged in N-dimensional graph layout. As a result of the work of his algorithm, each vertex is assigned coordinates in the N-dimensional space. However, he did not take into account that the accuracy may be lost when the results are saved in different formats. Now he must examine files to determine which of them contains which graph.
We are given two graphs — original one and one read from file. Due to conversion vertex coordinates of the second graph may be shifted, but no more than by a given ε. Vertex indexing may be changed as well.
It is required to compare given graphs and reconstruct correspondence between their vertices if possible.
Input data contains integer N — dimension of the space, V — number of vertices and E — number of edges.
Following is a set of the N ⋅ V coordinates of vertices of the original graph and set of the E edges specified by index pairs. Vertices are indexed from zero.
Next the second graph is given in the same format.
The ε precision is the last item of the input.
Output data must contain V integers Li — index of the second graph vertex corresponding to i-th vertex of the original graph.
If it is not possible to restore correspondences, the output a single number − 1.
Distance between any pair of vertices of the original graph is no less than 10 ⋅ ε, and all coordinates are in the range from − 10 to 10.
1 ≤ N ≤ 5, 1 ≤ V ≤ 2 ⋅ 104, 0 ≤ E ≤ 2 ⋅ V,
10 − 6 ≤ ε ≤ 1
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
| 2 | |
|