E. Inverse Topological Sort
time limit per test
1 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bobo recently learned the concept of topological ordering. One day, he observed a directed acyclic graph (DAG) $$$G=(V,E)$$$ with $$$|V|=n$$$ vertices numbered from $$$1$$$ to $$$n$$$, and immediately wrote down on the paper two sequences $$$A=(a_1,a_2,\dots,a_n)$$$ and $$$B=(b_1,b_2,\dots,b_n)$$$, such that $$$A$$$ is the lexicographically smallest topological ordering of $$$G$$$, and $$$B$$$ is the lexicographically largest topological ordering of $$$G$$$.

Unfortunately, now Bobo has forgotten what the original DAG $$$G$$$ looks like, and all he has is the two sequences $$$A$$$ and $$$B$$$. Can you help Bobo recover the original graph $$$G$$$? There might be multiple possible graphs corresponding to $$$A$$$ and $$$B$$$, or Bobo might write down the sequences incorrectly so that no valid graphs exist.

Refer to the note section for formal definitions of the underlined items.

Input

The first line of input contains an integer $$$n$$$ $$$(1\leq n\leq 10^5)$$$, denoting the length of the two sequences.

The second line of input contains $$$n$$$ pairwise distinct integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\leq a_i\leq n)$$$, denoting the first sequence $$$A$$$.

The second line of input contains $$$n$$$ pairwise distinct integers $$$b_1,b_2,\dots,b_n$$$ $$$(1\leq b_i\leq n)$$$, denoting the second sequence $$$B$$$.

Output

If there exists a directed graph $$$G$$$ that satisfies the condition, output "Yes" in the first line; otherwise, output "No" in the first line. You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will all be considered as positive replies.

If your answer is "Yes", output an integer $$$m$$$ $$$(0\leq m\leq \min(n(n-1)/2,10^6))$$$ in the first line. Then, in the following $$$m$$$ lines, output two integers $$$u,v$$$ $$$(1\leq u, v\leq n)$$$ each, denoting a directed edge $$$(u,v)$$$ in the graph $$$G$$$. The graph $$$G$$$ you output should satisfy that it is a directed acyclic graph, $$$A$$$ is the lexicographically smallest topological ordering of $$$G$$$, and $$$B$$$ is the lexicographically largest topological ordering of $$$G$$$. If multiple solutions exist, outputting any of them will be considered correct.

Note again that the graph you output must have no more than $$$10^6$$$ edges. It can be shown that if there exists any valid graph, there exists a valid one with no more than $$$10^6$$$ edges.

Examples
Input
3
1 2 3
1 2 3
Output
Yes
3
1 2
2 3
1 3
Input
3
1 2 3
3 2 1
Output
Yes
0
Input
3
3 2 1
1 2 3
Output
No
Note

Here, we provide formal definitions of some underlined items in the statement.

  • A topological ordering of a directed graph $$$G=(V,E)$$$ is a linear ordering (i.e., permutation) of its vertices such that for every directed edge $$$(u,v)\in E$$$ from vertex $$$u$$$ to vertex $$$v$$$, $$$u$$$ comes before $$$v$$$ in the ordering. It can be shown that a directed graph admits at least one topological ordering if and only if it is acyclic.
  • For two sequences $$$A=(a_1,a_2,\dots,a_n)$$$ and $$$B=(b_1,b_2,\dots,b_n)$$$ with the same length $$$n$$$, $$$A$$$ is said to be lexicographically smaller than $$$B$$$ if and only if there exists some index $$$1\leq i\leq n$$$, such that
    • $$$a_i \lt b_i$$$;
    • $$$a_j=b_j$$$ for all $$$j \lt i$$$.