A. Golden Dragons

Codeforces

IDCF10046A

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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. The 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. 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. 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. ## Input 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. ## Output 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. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of dragons and nests. Let $ 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) $. Let $ 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) $. **Constraints** 1. $ 1 \leq n \leq 5000 $ 2. Each dragon has at most $ a $ enemies: $ \deg_G(v) \leq a $ for all $ v \in V $ 3. Each nest has at most $ b $ neighbour nests: $ \deg_H(v) \leq b $ for all $ v \in V $ 4. $ n \geq 3ab $ **Objective** Find a bijection $ f: V \to V $ (a permutation assigning dragon $ i $ to nest $ f(i) $) such that: $$ \forall (u, v) \in E_D, \quad (f(u), f(v)) \notin E_N $$ In other words, no two enemy dragons are assigned to neighbour nests. Output "Solution exists" and such a permutation $ f $, or "Wrong answer" if none exists.

API Response (JSON)

{
  "problem": {
    "name": "A. Golden Dragons",
    "description": {
      "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 dr",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10046A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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 dr...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**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_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments