The Graph Permutation
/

## Algorithms, Graph, Graph Representation, approximate, homomorphism

Problem
Editorial
Analytics

You are given an undirected graph $G$ of $N$ vertices and $M$ edges. Additionally, you are given a set of $K$ edges. Your goal is to generate a permutation $P$ of $N$ integers such that if each node $i$ in the original graph is replaced by node $P[i]$ then the count of edges which belong to the set of $K$ edges and exist in the new graph as a cycle-edge should be maximized. An edge is a cycle-edge if it belongs to any cycle in the graph.

Input
The first line contains two space-separated integers $N$ and $M$. Next $M$ lines contain a pair of integers $(u,v)$ which denote that there is an edge between the two nodes in $u$ and $v$. Next line contains an integer $K$ which denotes count of edges in the new set. Now next $K$ lines each contain two space-separated integers $u$ and $v$ which denote the edge between node $u$ and $v$.
There are no multiple edges or self-loop in the graph.

Output
In the output, you need to print a permutation of first $N$ natural numbers (space-separated) that optimize the criteria in the statement above.

Constraints
$1 \le N \le 10^5$
$1 \le M , K \le 2 \times 10^5$
$1 \le u , v \le N$

Scoring
If $X$ count of edges out of $K$ satisfy the condition above then your score is given by $X / K$. Your solution will be considered better if you have more score.

Verdict
The output should contain exactly $N$ distinct natural numbers in the range $[1 , N]$. If your output meets the required format, you will be awarded an AC verdict with a score. In all other cases, you will receive either WA or RE.

SAMPLE INPUT
5 5
1 2
1 3
3 4
3 5
4 5
5
1 2
1 3
3 4
4 5
3 5

SAMPLE OUTPUT
1 2 3 4 5
Explanation

In the sample output, the permutation is 1 2 3 4 5 so it means that the new graph is similar to the old graph. There are 3 edges out of 5 in the new graph that belong to the cycle. So your score for this output is $3/5 = 0.6$. There may be other scores possible too with different permutations.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...