Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

It is time for the annual East(West)er Egg festival, where children across the country decorate their houses with painted eggs. For some unknown reason, they like to write numbers on the eggs they paint. Edward Elric painted $n$ eggs, and wrote a number from $1$ to $k$ on each of them. After painting them, he arranged the eggs in a line and left them in his room for the paint to dry.

After coming back, Edward discovered that someone touched his eggs, and although there are still $n$ eggs in a line, they are no longer in the same order as they were when he left them. He remembers the original order of the numbers written on the eggs. Now that the eggs have been reordered, he wants to know if all the eggs he painted still remain, or if one or more of them have surely been replaced with other ones.

The input consists of three lines. The first line contains $n$ and $k$, as described above.

The second line contains $n$ space-separated integers, each within the range $[1, k ]$, denoting the numbers written on the eggs in the order in which Edward left them in.

The third line contains $n$ space-separated integers, each within the range $[1, k]$, denoting the numbers written on the eggs in the order in which Edward found them.

**Constraints**

$1 \leq n, k \leq 10^5$

If one or more of Edward’s eggs were surely replaced, output “YES” (without the quotes). Otherwise, output “NO”, (without the quotes). Check the sample I/O for clarifications.

Input | Output |
---|---|

5 5 1 2 4 2 5 2 3 1 4 5 | YES |

There was no egg numbered 3 among Edward’s eggs. Since there is an egg numbered 3 now, at least one of these eggs must have been replaced. |

Input | Output |
---|---|

5 5 1 2 4 2 5 2 2 2 4 5 | YES |

In the original sequence, there were two eggs numbered 2. After Edward came back, he found three eggs numbered 2. Furthermore, Edward had one egg numbered 1, which he did not find after coming back. That means that at least one of the eggs were surely replaced. |

Input | Output |
---|---|

5 5 3 2 2 3 3 3 2 3 2 3 | NO |

Edward had 2 eggs coloured 2, and 3 eggs coloured 3 originally. After he came back, there were still 2 eggs coloured 2, and 3 eggs coloured 3. This shows that although the eggs have surely been rearranged, there is a possibility that all the eggs we find here are all Edward’s eggs. Since we cannot confirm that one or more eggs were replaced, we output “NO”. |

Input file can be very large, use faster I/O methods.

78% Solution Ratio

TanbeerEarliest,

user.804932Fastest, 0.0s

ShajibewucseLightest, 262 kB

mdvirusShortest, 424B

Login to submit