A. Love Triangle

Codeforces

IDCF939A

Time1000ms

Memory256MB

Difficulty—

graphs

English · Original

Chinese · Translation

Formal · Original

As you could know there are no male planes nor female planes. However, each plane on Earth likes some other plane. There are _n_ planes on Earth, numbered from 1 to _n_, and the plane with number _i_ likes the plane with number _f__i_, where 1 ≤ _f__i_ ≤ _n_ and _f__i_ ≠ _i_. We call a love triangle a situation in which plane _A_ likes plane _B_, plane _B_ likes plane _C_ and plane _C_ likes plane _A_. Find out if there is any love triangle on Earth. ## Input The first line contains a single integer _n_ (2 ≤ _n_ ≤ 5000) — the number of planes. The second line contains _n_ integers _f_1, _f_2, ..., _f__n_ (1 ≤ _f__i_ ≤ _n_, _f__i_ ≠ _i_), meaning that the _i_\-th plane likes the _f__i_\-th. ## Output Output «_YES_» if there is a love triangle consisting of planes on Earth. Otherwise, output «_NO_». You can output any letter in lower case or in upper case. [samples] ## Note In first example plane 2 likes plane 4, plane 4 likes plane 1, plane 1 likes plane 2 and that is a love triangle. In second example there are no love triangles.

正如你所知，飞机没有性别之分。然而，地球上每架飞机都喜欢另一架飞机。地球上共有 #cf_span[n] 架飞机，编号从 #cf_span[1] 到 #cf_span[n]，编号为 #cf_span[i] 的飞机喜欢编号为 #cf_span[fi] 的飞机，其中 #cf_span[1 ≤ fi ≤ n] 且 #cf_span[fi ≠ i]。我们称一个“爱情三角形”为一种情况：飞机 #cf_span[A] 喜欢飞机 #cf_span[B]，飞机 #cf_span[B] 喜欢飞机 #cf_span[C]，飞机 #cf_span[C] 喜欢飞机 #cf_span[A]。请判断地球上是否存在这样的爱情三角形。第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 5000]) —— 飞机的数量。第二行包含 #cf_span[n] 个整数 #cf_span[f1, f2, ..., fn] (#cf_span[1 ≤ fi ≤ n], #cf_span[fi ≠ i])，表示第 #cf_span[i] 架飞机喜欢第 #cf_span[fi] 架飞机。如果存在由地球上的飞机组成的爱情三角形，请输出 «_YES_»；否则输出 «_NO_»。你可以使用任意大小写字母输出。在第一个例子中，飞机 #cf_span[2] 喜欢飞机 #cf_span[4]，飞机 #cf_span[4] 喜欢飞机 #cf_span[1]，飞机 #cf_span[1] 喜欢飞机 #cf_span[2]，构成一个爱情三角形。在第二个例子中，不存在爱情三角形。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 5000]) —— 飞机的数量。第二行包含 #cf_span[n] 个整数 #cf_span[f1, f2, ..., fn] (#cf_span[1 ≤ fi ≤ n], #cf_span[fi ≠ i])，表示第 #cf_span[i] 架飞机喜欢第 #cf_span[fi] 架飞机。 ## Output 如果存在由地球上的飞机组成的爱情三角形，请输出 «_YES_»；否则输出 «_NO_»。你可以使用任意大小写字母输出。 [samples] ## Note 在第一个例子中，飞机 #cf_span[2] 喜欢飞机 #cf_span[4]，飞机 #cf_span[4] 喜欢飞机 #cf_span[1]，飞机 #cf_span[1] 喜欢飞机 #cf_span[2]，构成一个爱情三角形。在第二个例子中，不存在爱情三角形。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of planes, with $ 2 \leq n \leq 5000 $. Let $ f: \{1, 2, \dots, n\} \to \{1, 2, \dots, n\} $ be a function such that $ f(i) \neq i $ for all $ i $, representing the plane that plane $ i $ likes. **Constraints** For all $ i \in \{1, \dots, n\} $: - $ 1 \leq f(i) \leq n $ - $ f(i) \neq i $ **Objective** Determine whether there exist distinct indices $ a, b, c \in \{1, \dots, n\} $ such that: $$ f(a) = b, \quad f(b) = c, \quad f(c) = a $$ If such a triple exists, output "YES"; otherwise, output "NO".

Samples

Input #1

5
2 4 5 1 3

Output #1

YES

Input #2

5
5 5 5 5 1

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "A. Love Triangle",
    "description": {
      "content": "As you could know there are no male planes nor female planes. However, each plane on Earth likes some other plane. There are _n_ planes on Earth, numbered from 1 to _n_, and the plane with number _i_ ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF939A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "As you could know there are no male planes nor female planes. However, each plane on Earth likes some other plane. There are _n_ planes on Earth, numbered from 1 to _n_, and the plane with number _i_ ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "正如你所知，飞机没有性别之分。然而，地球上每架飞机都喜欢另一架飞机。地球上共有 #cf_span[n] 架飞机，编号从 #cf_span[1] 到 #cf_span[n]，编号为 #cf_span[i] 的飞机喜欢编号为 #cf_span[fi] 的飞机，其中 #cf_span[1 ≤ fi ≤ n] 且 #cf_span[fi ≠ i]。\n\n我们称一个“爱情三角形”为一种情况：飞机 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of planes, with $ 2 \\leq n \\leq 5000 $.  \nLet $ f: \\{1, 2, \\dots, n\\} \\to \\{1, 2, \\dots, n\\} $ be a function such that $ f(i) \\neq i $ for all ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments