Farmer John has \(N\) barns (\(3\le N\le 5\cdot 10^5\)), of which \(K\)
(\(3\le K\le N\)) distinct pairs of barns are connected.

First, Annabelle assigns each barn a distinct integer label in the range
\([1,N]\), and observes that the barns with labels \(a_1,\dots,a_K\) are connected
in a cycle, in that order. That is, barns \(a_i\) and \(a_{i+1}\) are connected for
all \(1\le i, and barns \(a_K\) and \(a_1\) are also connected. All \(a_i\) are
distinct.

Next, Bessie also assigns each barn a distinct integer label in the range
\([1,N]\) and observes that the barns with labels \(b_1,\dots,b_K\) are connected in
a cycle, in that order. All \(b_i\) are distinct.

Some (possibly none or all) barns are assigned the same label by Annabelle and
Bessie. Compute the maximum possible number of barns that are assigned the same
label by Annabelle and Bessie.

Problem credits: Benjamin Qi

SCORING

• Inputs 4-5: \(N \le 8\)
• Inputs 6-8: \(N \le 5000\)
• Inputs 9-15: No additional constraints

Problem credits: Benjamin Qi

The first line contains \(N\) and \(K\).

The next line contains \(a_1,\dots, a_K\).

The next line contains \(b_1,\dots, b_K\).

The maximum number of fixed points.

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > December > Silver