{"raw_statement":[{"iden":"statement","content":"Golden dragons are immortal majestic creatures inhabiting Enia since the beginning of times. There are total of n golden dragons in Enia, each one in its own nest. The problem is that some pairs of dragons dislike each other, whereas some pairs of nests are so close to each other that if one roars in one of the nests, it will be clearly heard in another one. Each dragon has at most a enemies, and each nest has at most b neighbour nests. It is also known that n ≥ 3ab.\n\nThe dragons are annoyed at the roar of their enemies, so they want to resettle so that each dragon would occupy exactly one nest, and no two enemy dragons would live in neighbour nests.\n\nThe first line contains the single integer n (1 ≤ n ≤ 5000) — the number of dragons.\n\nThe second line contains the single integer m () — the number of pairs of enemy dragons. Each of the next m lines contains two integers separated by the space: xj and yj (1 ≤ xj < yj ≤ n) — the pair of numbers of two enemy dragons. Each pair occurs only once.\n\nThe next line contains the single integer k () — the number of pairs of neighbour nests. Each of the next k lines contains two integers separated by the space: pj and qj (1 ≤ pj < qj ≤ n) — the pair of numbers of two neighbour nests. Each pair occurs only once.\n\nIn the first line output «_Solution exists_» (without quotes) if there exists a variant of resettling dragons satisfying the problem's condition. Otherwise output «_Wrong answer_» (without quotes).\n\nIn the first case in the second line output n integers di separated by the spaces, where di is the number of the dragon which should be settled in the i-th nest. If there are multiple answers, output any of them.\n\n"},{"iden":"input","content":"The first line contains the single integer n (1 ≤ n ≤ 5000) — the number of dragons.The second line contains the single integer m () — the number of pairs of enemy dragons. Each of the next m lines contains two integers separated by the space: xj and yj (1 ≤ xj < yj ≤ n) — the pair of numbers of two enemy dragons. Each pair occurs only once.The next line contains the single integer k () — the number of pairs of neighbour nests. Each of the next k lines contains two integers separated by the space: pj and qj (1 ≤ pj < qj ≤ n) — the pair of numbers of two neighbour nests. Each pair occurs only once."},{"iden":"output","content":"In the first line output «_Solution exists_» (without quotes) if there exists a variant of resettling dragons satisfying the problem's condition. Otherwise output «_Wrong answer_» (without quotes).In the first case in the second line output n integers di separated by the spaces, where di is the number of the dragon which should be settled in the i-th nest. If there are multiple answers, output any of them."},{"iden":"examples","content":"Input311 211 3OutputSolution exists2 1 3 Input421 23 421 32 4OutputSolution exists1 2 3 4 "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of dragons and nests.  \nLet $ G = (V, E_D) $ be the *enemy graph*, where $ V = \\{1, \\dots, n\\} $, and $ E_D $ is the set of enemy pairs $ (x_j, y_j) $.  \nLet $ H = (V, E_N) $ be the *neighbour nest graph*, where $ V = \\{1, \\dots, n\\} $, and $ E_N $ is the set of neighbour nest pairs $ (p_j, q_j) $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 5000 $  \n2. Each dragon has at most $ a $ enemies: $ \\deg_G(v) \\leq a $ for all $ v \\in V $  \n3. Each nest has at most $ b $ neighbour nests: $ \\deg_H(v) \\leq b $ for all $ v \\in V $  \n4. $ n \\geq 3ab $  \n\n**Objective**  \nFind a bijection $ f: V \\to V $ (a permutation assigning dragon $ i $ to nest $ f(i) $) such that:  \n$$\n\\forall (u, v) \\in E_D, \\quad (f(u), f(v)) \\notin E_N\n$$  \nIn other words, no two enemy dragons are assigned to neighbour nests.  \n\nOutput \"Solution exists\" and such a permutation $ f $, or \"Wrong answer\" if none exists.","simple_statement":"There are n dragons and n nests. Some dragons are enemies, and some nests are neighbors. Each dragon must move to one nest. No enemy dragons can be in neighbor nests. Find any valid assignment, or say it's impossible.","has_page_source":false}