English · Original
Chinese · Translation
Formal · Original
Earlier, when there was no Internet, each bank had a lot of offices all around Bankopolis, and it caused a lot of problems. Namely, each day the bank had to collect cash from all the offices.
Once Oleg the bank client heard a dialogue of two cash collectors. Each day they traveled through all the departments and offices of the bank following the same route every day. The collectors started from the central department and moved between some departments or between some department and some office using special roads. Finally, they returned to the central department. The total number of departments and offices was _n_, the total number of roads was _n_ - 1. In other words, the special roads system was a rooted tree in which the root was the central department, the leaves were offices, the internal vertices were departments. The collectors always followed the same route in which the number of roads was minimum possible, that is 2_n_ - 2.
One of the collectors said that the number of offices they visited between their visits to offices _a_ and then _b_ (in the given order) is equal to the number of offices they visited between their visits to offices _b_ and then _a_ (in this order). The other collector said that the number of offices they visited between their visits to offices _c_ and then _d_ (in this order) is equal to the number of offices they visited between their visits to offices _d_ and then _c_ (in this order). The interesting part in this talk was that the shortest path (using special roads only) between any pair of offices among _a_, _b_, _c_ and _d_ **passed through the central department**.
Given the special roads map and the indexes of offices _a_, _b_, _c_ and _d_, determine if the situation described by the collectors was possible, or not.
## Input
The first line contains single integer _n_ (5 ≤ _n_ ≤ 5000) — the total number of offices and departments. The departments and offices are numbered from 1 to _n_, the central office has index 1.
The second line contains four integers _a_, _b_, _c_ and _d_ (2 ≤ _a_, _b_, _c_, _d_ ≤ _n_) — the indexes of the departments mentioned in collector's dialogue. It is guaranteed that these indexes are offices (i.e. leaves of the tree), not departments. It is guaranteed that the shortest path between any pair of these offices passes through the central department.
On the third line _n_ - 1 integers follow: _p_2, _p_3, ..., _p__n_ (1 ≤ _p__i_ < _i_), where _p__i_ denotes that there is a special road between the _i_\-th office or department and the _p__i_\-th department.
Please note the joint enumeration of departments and offices.
It is guaranteed that the given graph is a tree. The offices are the leaves, the departments are the internal vertices.
## Output
If the situation described by the cash collectors was possible, print "_YES_". Otherwise, print "_NO_".
[samples]
## Note
In the first example the following collector's route was possible: . We can note that between their visits to offices _a_ and _b_ the collectors visited the same number of offices as between visits to offices _b_ and _a_; the same holds for _c_ and _d_ (the collectors' route is infinite as they follow it each day).
In the second example there is no route such that between their visits to offices _c_ and _d_ the collectors visited the same number of offices as between visits to offices _d_ and _c_. Thus, there situation is impossible.
In the third example one of the following routes is: .
早些年还没有互联网时，每家银行在银行城都有大量分支机构，这带来了许多问题。具体来说，每天银行都需要从所有分支机构收集现金。
有一次，银行客户 Oleg 听到两名现金收集员的对话。每天他们都会沿着同一条路线遍历银行的所有部门和分支机构。收集员从中央部门出发，通过专用道路在部门之间或部门与分支机构之间移动，最终返回中央部门。部门和分支机构的总数为 $n$，专用道路的总数为 $n - 1$。换句话说，专用道路系统是一棵以中央部门为根的有根树，叶子是分支机构，内部节点是部门。收集员始终遵循一条道路数量最少的路线，即 $2n - 2$ 条道路。
其中一名收集员说，在他们访问分支机构 $a$ 之后、再访问分支机构 $b$ 的过程中，经过的分支机构数量，等于在访问 $b$ 之后、再访问 $a$ 的过程中经过的分支机构数量。另一名收集员说，在他们访问分支机构 $c$ 之后、再访问分支机构 $d$ 的过程中，经过的分支机构数量，等于在访问 $d$ 之后、再访问 $c$ 的过程中经过的分支机构数量。有趣的是，任意一对属于 $a$、$b$、$c$、$d$ 的分支机构之间的最短路径（仅使用专用道路）都经过中央部门。
给定专用道路的地图以及分支机构 $a$、$b$、$c$ 和 $d$ 的编号，请判断收集员所描述的情况是否可能。
第一行包含一个整数 $n$（$5 ≤ n ≤ 5000$）——分支机构和部门的总数。部门和分支机构编号从 $1$ 到 $n$，中央部门编号为 $1$。
第二行包含四个整数 $a$、$b$、$c$ 和 $d$（$2 ≤ a, b, c, d ≤ n$）——收集员对话中提到的分支机构编号。保证这些编号是分支机构（即树的叶子），而非部门。保证任意两个上述分支机构之间的最短路径都经过中央部门。
第三行包含 $n - 1$ 个整数：$p_2, p_3, ..., p_n$（$1 ≤ p_i < i$），其中 $p_i$ 表示第 $i$ 个分支机构或部门与第 $p_i$ 个部门之间有一条专用道路。
请注意，部门和分支机构采用统一编号。
保证给定图是一棵树。分支机构是叶子，部门是内部节点。
如果收集员描述的情况是可能的，输出 "_YES_"；否则输出 "_NO_"。
在第一个例子中，可能存在如下收集员路线：。我们可以注意到，在访问分支机构 $a$ 和 $b$ 之间，收集员经过的分支机构数量等于在访问 $b$ 和 $a$ 之间经过的数量；对 $c$ 和 $d$ 同样成立（收集员的路线是无限循环的，他们每天重复此路线）。
在第二个例子中，不存在一条路线使得在访问 $c$ 和 $d$ 之间经过的分支机构数量等于在访问 $d$ 和 $c$ 之间经过的数量。因此这种情况不可能。
在第三个例子中，其中一条可能路线是：。
## Input
第一行包含一个整数 $n$（$5 ≤ n ≤ 5000$）——分支机构和部门的总数。部门和分支机构编号从 $1$ 到 $n$，中央部门编号为 $1$。第二行包含四个整数 $a$、$b$、$c$ 和 $d$（$2 ≤ a, b, c, d ≤ n$）——收集员对话中提到的分支机构编号。保证这些编号是分支机构（即树的叶子），而非部门。保证任意两个上述分支机构之间的最短路径都经过中央部门。第三行包含 $n - 1$ 个整数：$p_2, p_3, ..., p_n$（$1 ≤ p_i < i$），其中 $p_i$ 表示第 $i$ 个分支机构或部门与第 $p_i$ 个部门之间有一条专用道路。请注意，部门和分支机构采用统一编号。保证给定图是一棵树。分支机构是叶子，部门是内部节点。
## Output
如果收集员描述的情况是可能的，输出 "_YES_"；否则输出 "_NO_"。
[samples]
## Note
在第一个例子中，可能存在如下收集员路线：。我们可以注意到，在访问分支机构 $a$ 和 $b$ 之间，收集员经过的分支机构数量等于在访问 $b$ 和 $a$ 之间经过的数量；对 $c$ 和 $d$ 同样成立（收集员的路线是无限循环的，他们每天重复此路线）。在第二个例子中，不存在一条路线使得在访问 $c$ 和 $d$ 之间经过的分支机构数量等于在访问 $d$ 和 $c$ 之间经过的数量。因此这种情况不可能。在第三个例子中，其中一条可能路线是：。
**Definitions**
Let $ T = (V, E) $ be a rooted tree with $ n $ vertices, where:
- $ V = \{1, 2, \dots, n\} $, with vertex $ 1 $ as the root (central department).
- Leaves $ L \subset V $ are offices; internal nodes are departments.
- Given distinct leaves $ a, b, c, d \in L \setminus \{1\} $.
- The path between any pair among $ \{a, b, c, d\} $ passes through the root $ 1 $.
Let $ R $ be a closed walk (Eulerian tour) of the tree that traverses each edge exactly twice (minimum-length route visiting all nodes and returning to root), corresponding to the collectors’ daily route.
Let $ \text{visit}(x) $ denote the sequence of leaf visits in $ R $, ordered by time.
For any two distinct leaves $ x, y $, define $ \text{between}(x, y) $ as the number of offices (leaves) visited strictly between the first occurrence of $ x $ and the next occurrence of $ y $ in the cyclic sequence $ \text{visit}(\cdot) $.
**Constraints**
1. $ 5 \leq n \leq 5000 $
2. $ a, b, c, d \in L $, $ a, b, c, d \neq 1 $, all distinct.
3. For all pairs $ (x, y) \in \{(a,b), (a,c), (a,d), (b,c), (b,d), (c,d)\} $, the unique path from $ x $ to $ y $ in $ T $ passes through vertex $ 1 $.
4. The tree is given via parent array $ p_2, p_3, \dots, p_n $, where $ p_i $ is the parent of vertex $ i $.
**Objective**
Determine whether there exists a valid Eulerian tour $ R $ such that:
$$
\text{between}(a, b) = \text{between}(b, a) \quad \text{and} \quad \text{between}(c, d) = \text{between}(d, c)
$$
Output "YES" if such a tour exists; otherwise, output "NO".
API Response (JSON)
{
"problem": {
"name": "E. Problem of offices",
"description": {
"content": "Earlier, when there was no Internet, each bank had a lot of offices all around Bankopolis, and it caused a lot of problems. Namely, each day the bank had to collect cash from all the offices. Once Ol",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF793E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Earlier, when there was no Internet, each bank had a lot of offices all around Bankopolis, and it caused a lot of problems. Namely, each day the bank had to collect cash from all the offices.\n\nOnce Ol...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "早些年还没有互联网时，每家银行在银行城都有大量分支机构，这带来了许多问题。具体来说，每天银行都需要从所有分支机构收集现金。\n\n有一次，银行客户 Oleg 听到两名现金收集员的对话。每天他们都会沿着同一条路线遍历银行的所有部门和分支机构。收集员从中央部门出发，通过专用道路在部门之间或部门与分支机构之间移动，最终返回中央部门。部门和分支机构的总数为 $n$，专用道路的总数为 $n - 1$。换句话说，...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ T = (V, E) $ be a rooted tree with $ n $ vertices, where: \n- $ V = \\{1, 2, \\dots, n\\} $, with vertex $ 1 $ as the root (central department). \n- Leaves $ L \\subset V $ are off...",
"is_translate": false,
"language": "Formal"
}
]
}