# SCCP20260108

改めて、あけましておめでとうございます。4Q残りの課プロもあまり気負わずバチャを楽しんでくれると幸いです。

https://kenkoooo.com/atcoder/#/contest/show/821a78c2-ab61-4852-a48e-f61f0f13e27f

## A: A to Z String 2

https://atcoder.jp/contests/abc257/tasks/abc257_a

ぱっと思いつく方法の一つに、文字列を実際に作ってその$X$番目の文字にアクセスするというものがあると思います。今回の問題では$N$が小さいためこの方法で問題ありません。

#include <iostream>
#include <string>
using namespace std;
int main() {
	int N, X;
	cin >> N >> X;
	string S;
	for (char c = 'A' ; c <= 'Z' ; c++) {
		S += string(N, c);
	}
	char ans = S[X - 1]; // 0-indexedに注意!
	cout << ans << '\n';
}

$0, 1, \dots, N - 1$番目の文字は`A`、$N, N + 1, \dots, 2N - 1$番目の文字は`B`...と考えていくと、$X$番目の文字(0-indexed)は$\lfloor \frac{X}{N}\rfloor$番目のアルファベットであることがわかります。

#include <iostream>
using namespace std;
int main() {
    int N, X;
    cin >> N >> X;
    // i番目のアルファベット大文字をchar型で表現するためには、'A' + iとする
    char ans = 'A' + (X - 1) / N;
    cout << ans << '\n';
}

どっちの方針も素敵ですね。

## B: Pasta

問題文通りにシミュレーションを書き下します。食べたパスタを削除することを明示的に行うと以下のような実装になります。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int N, M;
	cin >> N >> M;
	vector<int> A(N), B(M);
	for (int& a : A) {
		cin >> a;
	}
	for (int& b : B) {
		cin >> b;
	}
	for (int b : B) {
		auto it = find(A.begin(), A.end(), b);
		if (it == A.end()) {
			cout << "No\n";
			return 0;
		}
		A.erase(it);
	}
	cout << "Yes\n";
}

これでACすることができます。

時間計算量は一重ループしていないので$O(N + M)$...と言いたいですが、実際は`find`と`erase`でそれぞれ$\Theta (N)$かかっていますので、$\Theta (MN)$です。
- https://cpprefjp.github.io/reference/algorithm/find.html
- https://cpprefjp.github.io/reference/vector/vector/erase.html

また、`erase`はC言語likeな配列では使えないことに注意する必要がありそうです。なぜなら、配列は固定長だから。

これはもし$N$と$M$が$2\times 10^5$程度まで大きな値を取りうる場合、TLEになってしまうことを示唆しています。以下のようにすると$O(N + M)$に改善できるでしょう。
- `unordered_map`を用いて**バケット**を構築することで、`find`の手間を無くす

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
	int N, M;
	cin >> N >> M;
	unordered_map<int, vector<int>> A;
	for (int i = 0 ; i < N ; i++) {
		int a;
		cin >> a;
		A[a].push_back(i);
	}
	vector<int> B(M);
	for (int& b : B) {
		cin >> b;
	}
	for (int b : B) {
		if (A[b].empty()) {
			cout << "No\n";
			return 0;
		}
		A[b].pop_back();
	}
	cout << "Yes\n";
}

## C: Dango

ダンゴ文字列の末尾の`-`の位置を固定して、それより前、または後ろに最大何個の`o`をつなげられるか？ということを実装に起こします。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	int N;
	string S;
	cin >> N >> S;
	int ans = -1;
	for (int i = 0 ; i < 2 ; i++) {
		for (int j = 0 ; j < N ; j++) {
			if (S[j] == '-') {
				int k = j + 1;
				while (k < N and S[k] == 'o') {
					k++;
				}
				int level = k - j - 1;
				if (level > 0) {
					ans = max(level, ans);
				}
			}
		}
		reverse(S.begin(), S.end());
	}
	cout << ans << '\n';
}

以上の実装では各`-`に対してその後ろに最大何個の`o`をくっつけることができるのか？ということを探索しています。$i$のループの最後で$S$をreverseすることにより、「前に`o`をくっつけるパターン」をまったく同じ方法で探索することに成功しています。

このコードの計算量は$j$のループと$k$のループ二重ループで$\Theta(N^2)$に見えなくもないですが、実際は$O(N)$です。$k$は$j$のループ全体で整数$0, 1, \dots, N - 1$のそれぞれになるタイミングが高々一回しかないことから従います。もっと平易な言葉で言うと、各`o`は$j$一回のループで高々一個のダンゴ文字列にしか寄与していないことから従います。

## D: Union of Intervals


端的に言うと、一つ以上の区間でおおわれている要素の極大な区間たちを列挙してという話です。
$1\le L_i\lt R_i\le 2\times 10^5$という制約を踏まえると、以下の二つができればよいです。

ステップ1: 整数$1, 2, \dots, 2\times 10^5$について各要素が$1$個以上の区間に覆われているか判定する
ステップ2: ↑を満たす極大な区間を列挙する

### ステップ1: imos法

ステップ1を素直に実装すると以下のような感じになると思いますが、これはTLEします。

int M = 200000;
vector<int> cnt(M + 1);
for (int i = 0 ; i < N ; i++) {
	int L, R;
	cin >> L >> R;
	for (int j = L ; j < R ; j++) {
		cnt[j]++;
	}
}
for (int i = 1 ; i <= M ; i++) {
	if (cnt[i] >= 1) {
		// iは一個以上の区間に覆われている
	}
}

例えば全部の区間が$L = 1, R = 200000$であるときにワーストケースを引いていて、計算量は$\Theta(N^2)$です。

「区間に加算を行う、すべての区間の加算後に各点の値を取得する」という状況ではimos法が有効です。


足される値の変化量(画像下)に注目すると、これは$2N$個しかありません。このような加算を行ってから、累積和を取ると画像上の加算を実現することができています。数学にフレンドリーな方たちは積分しているとイメージするとわかりやすいらしいです。

### ステップ2: うまくループを回す

尺取り法と呼ばれるテクニックの一種だとは思うのですが、本当に尺取り法が自信が無いため、尺取り法の解説はここではしません。実装例も踏まえて口頭で説明します。

### 実装例

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int> cnt(200020);
	while (N--) {
		int L, R;
		cin >> L >> R;
		cnt[L]++;
		cnt[R]--;
	}
	for (int i = 1 ; i < ssize(cnt) ; i++) {
		cnt[i] += cnt[i - 1];
	}
	vector<bool> B(cnt.size());
	for (int i = 0 ; i < ssize(cnt) ; i++) {
		B[i] = cnt[i] >= 1;
	}
	for (int l = 0, r = 0 ; l < ssize(B) ; l = r) {
		while (r < ssize(B) and B[l] == B[r]) {
			r++;
		}
		if (B[l]) {
			cout << l << ' ' << r << '\n';
		}
	}
}

## E: XX to XXX

「特定の操作を$0$回以上繰り返すことで目標を達成できるか？」という問題はまず操作の特徴を把握することから始めます。

どのような特徴を探せばいいのか？と言われると少し困ってしまいますが、例えば以下のような回答があるでしょう
- どのような操作であっても「変わらないもの」(不変量)
- 一つ以上の操作を組み合わせて作る「意味づけのできる操作」
- などなど

兎にも角にも操作を観察してみましょう。

abbaacc -> abbbaacc -> abbbaaacc -> abbbaaaacc -> ....

ここでは変わらないものとして、「同じ文字のブロックの並び」が挙げられます。上の操作の例ではどのように操作を行っても「$a$が一個以上 -> $b$が一個以上 -> $a$が一個以上 -> $c$が一個以上」という文字のブロックの構造を崩すことができません。

ABAC -> ABAC -> ABAC -> ABAC -> ...

$S$に何回操作を施してもこの並びの構造を変えることができないということは、$S$と$T$でこの並びが異なった時点で$S$と$T$を揃えることができません。

並びの構造が同じであることと答えが`Yes`になることは同値でしょうか？いいえ。必要十分ではありますが、十分条件ではありません。各同じ文字のブロックの文字数に注目しましょう。
- ブロックの長さが$1$なら、その長さを変えることはできない
- ブロックの長さは操作によって増えるばかりで、減らすことはできない。

という特徴があります。つまり、それぞれ対応するブロックについて
- 文字が同じ
- $S$に関するブロックの文字数が$1$ならば、$T$のそれの長さも$1$である
- $S$に関するブロックの長さは$T$のそれ以下である

という$3$条件を同時に満たすことが必要条件となります。例えばサンプル$1$だと

abbaac (aが一つ)(bが二つ)(aが二つ)(cが一つ)
abbbbaaac (aが一つ)(bが四つ)(aが三つ)(cが一つ)

となり、$3$条件が満たされていることがわかります。

#include <vector>
using namespace std;
pair<string, vector<int>> RLE(string S) {
    string val;
    vector<int> len;
    for (char c : S) {
        if (val.empty() or val.back() != c) {
            val += c;
            len.push_back(1);
        }
        else {
            len.back()++;
        }
    }
    return {val, len};
}
int main() {
    string S, T;
    cin >> S >> T;
    auto [sval, slen] = RLE(S);
    auto [tval, tlen] = RLE(T);
    if (sval != tval) {
        cout << "No\n";
    }
    else {
        bool ok = true;
        for (int i = 0 ; i < ssize(slen) ; i++) {
            if (slen[i] > tlen[i])
                ok = false;
            else if (slen[i] == 1 and slen[i] < tlen[i])
                ok = false;
        }
        cout << (ok ? "Yes\n" : "No\n");
    }
}

連続する同じ文字を(文字、何回連続するか)というペアに変換する操作を連長圧縮(Run Length Encoding)と呼ぶことが多いです。このRLEは競プロでの方言としてのRLEで、本来の文脈でのRLEとはやっていることが若干違うようです。
- https://ja.wikipedia.org/wiki/%E9%80%A3%E9%95%B7%E5%9C%A7%E7%B8%AE

## F: 魔法陣 (Magic Circles)

想定解法よりもスマートさに欠けますが、ある程度典型を振り回した解法をヒント式で提示します。

<details>
<summary>ヒント1</summary>

一つのクエリをグラフの最短路に帰着させましょう。$N$頂点$O(N^2)$辺のグラフを構築し、クエリ毎に律儀にBFSすることで、小課題1, 5に正解することができます。

</details>

<details>
<summary>ヒント2</summary>

$O(N)$頂点$O(N)$辺のグラフであってヒント1で作ったものと等価なグラフを作ってください。相変わらず小課題1, 5にしか正解できませんが、計算量が$O(QN)$になるように頑張って。

</details>

<details>
<summary>ヒント2の答え</summary>

図は公式解説から引用


赤のワープと青のワープに対応する超頂点を作ります。$N + 2$頂点$O(N)$辺です。

</details>

<details>
<summary>ヒント3</summary>

- ワープをせず$X_i$から$Y_i$へ移動する
- $X_i$から赤の超頂点へ最短で移動し、赤の超頂点から$Y_i$へ最短で移動する
- $X_i$から青の超頂点へ最短で移動し、青の超頂点から$Y_i$へ最短で移動する

の三つのシナリオですべて尽くされます。

</details>

<details>
<summary>ヒント4</summary>

赤の超頂点から他頂点への最短経路と青の超頂点から他頂点への最短経路を前計算してみます。これは$O(N\log N)$や$O(N)$でできます。

すると、二つ目のシナリオの「赤の超頂点から$Y_i$へ最短で移動する」と三つ目のシナリオの「青の超頂点から$Y_i$へ最短で移動する」は$O(1)$で取得できるようになります。

</details>

<details>
<summary>ヒント5</summary>

後は$X_i$から赤、青の超頂点までの最短距離(*)が各クエリ毎に計算できれば良いです。二分探索(`lower_bound`の類)を用いると$O(\log N)$でできます。

</details>

<details>

<summary>実装例</summary>

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <tuple>
#include <ranges>
#include <queue>
using namespace std;
int main() {
    int N, Q;
    string S;
    cin >> N >> Q >> S;
    const int RED = N, BLUE = N + 1; // 赤、青のワープに対応する超頂点
    // 0.5は浮動小数点型において丸め誤差無しで表現できるので、doubleでok
    // https://www.cc.kyoto-su.ac.jp/~yamada/programming/float.html
    vector<vector<pair<int,double>>> g(N + 2); 
    for (int i = 0 ; i < N ; i++) {
        g[i].push_back({(i + 1) % N, 1});
        g[i].push_back({(i - 1 + N) % N, 1});
        if (S[i] == 'r') {
            g[i].push_back({RED, 0.5});
            g[RED].push_back({i, 0.5});
        }
        else {
            g[i].push_back({BLUE, 0.5});
            g[BLUE].push_back({i, 0.5});
        }
    }
    auto dijkstra = [&](int s) -> vector<double> {
        vector<double> res(g.size(), 1e20);
        res[s] = 0;
        using qt = pair<double, int>;
        priority_queue<qt, vector<qt>, greater<qt>> que;
        que.push({res[s], s});
        while (que.size()) {
            auto [d, v] = que.top();
            que.pop();
            if (res[v] < d) {
                continue;
            }
            for (auto [x, w] : g[v]) {
                if (res[x] > d + w) {
                    res[x] = d + w;
                    que.push({res[x], x});
                }
            }
        }
        return res;
    };
    vector<vector<double>> dist(2);
    dist[0] = dijkstra(RED);
    dist[1] = dijkstra(BLUE);
    vector<int> reds, blues;
    // r, bの場所をreds, bluesに保管しておき、はじめにワープするまでの最短距離の計算に利用
    for (int i = 0 ; i < 3 * N ; i++) {
        if (S[i % N] == 'r') {
            reds.push_back(i);
        }
        else {
            blues.push_back(i);
        }
    }
    while (Q--) {
        int X, Y;
        cin >> X >> Y;
        X--; Y--;
        int ans = (int)1e9;
        // ワープをしないケース
        ans = min(ans, abs(Y - X));
        ans = min(ans, X + N - Y);
        ans = min(ans, Y + N - X);
        X += N;
        // 青のワープより先に赤のワープを使うケース、赤のワープのみ使用するケース
        if (reds.size()) {
            auto it = ranges::lower_bound(reds, X) - reds.begin();
            assert(0 < it and it < ssize(reds));
            ans = min<int>(ans, reds[it] - X + 0.5 + dist[0][Y]);
            ans = min<int>(ans, X - reds[it - 1] + 0.5 + dist[0][Y]);
        }
        // 赤のワープより先に青のワープを使うケース、青のワープのみ使用するケース
        if (blues.size()) {
            auto it = ranges::lower_bound(blues, X) - blues.begin();
            assert(0 < it and it < ssize(blues));
            ans = min<int>(ans, blues[it] - X + 0.5 + dist[1][Y]);
            ans = min<int>(ans, X - blues[it - 1] + 0.5 + dist[1][Y]);
        }
        cout << ans << '\n';
    }
}

</details>

<details>
<summary>余談</summary>

公式解説にもある通り、解が常に$3$以下であることに注目すると、これまでのヒントのような面倒なことはしなくても解けます(え？)

これまでのヒントで提示された「いくつかの頂点について、その頂点を始点とした最短路を前計算して、クエリで利用する」というアイデアは汎用的に使えるものだと思います。

類題: https://codeforces.com/contest/1860/problem/E

</details>

## G: Box in Box

<details>
<summary>ヒント1</summary>

条件を満たす二つの箱について、どのような回転を行うと片方がもう片方に入るようになりますか？

</details>

<details>
<summary>ヒント2</summary>

ヒント1の答えは$h_i\le w_i\le d_i$となるように回転する。でした。

以後全ての箱が$h_i\le w_i\le d_i$を満たすとして、箱を回転しないで条件を満たすペアが存在するか判定できれば良いです。

</details>

<details>
<summary>ヒント3</summary>

$h_i$で箱をソートするといくらか条件が簡単になります。

同じ長さを許容するというちょっと簡単な問題を考えましょう。条件を満たす箱のペア $(i, j)$とは
- $1\le i\lt j\le N$
- $w_i\le w_j$
- $d_i\le d_j$

の三つを同時に満たすことと同値となります。

</details>

<details>
<summary>ヒント4</summary>

$1, 2, \dots, N$の順に$j$を固定してみます。$j$に対して条件を満たす$i$を高速に見つけることができるでしょうか？

</details>

<details>
<summary>ヒント5</summary>

$w_i$を添え字として何らかの情報を管理させます。そういうデータ構造を考えます。$w$を座圧しておくとなお良いでしょう。

</details>

<details>
<summary>ヒント5</summary>

$j$を固定しています。ヒント5で取り上げたデータ構造に関して、$w_i\le w_j$を満たす添え字$w_i$の集合というのはデータ構造のprefixということになります。

データ構造のprefixから$d_i\le d_j$を満たす$i$があるか判定できれば良いです。

</details>

<details>
<summary>ヒント6</summary>

データ構造の添え字$w'$に$w_i = w'$を満たす$i$の中で$d_i$が最小なものを持たせます。ヒント5はprefix最小値に帰着しています -> セグ木

</details>

<details>
<summary>ヒント7</summary>

これを等号を許さないバージョンにするのは、頑張りましょう。最近のABC-Eにそういうのをうまくやるテクがあったような気がします。(下の実装例では使っていませんが....)

</details>

<details>
<summary>実装例</summary>

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <tuple>
#include <ranges>
#include <queue>
using namespace std;
const int INF = (int)2e9;
struct SegTree {
    int n;
    vector<int> a;
    SegTree(int N) : n{N}, a(n << 1, INF) {}
    void chmin(int i, int v) {
        assert(0 <= i and i < n);
        i += n;
        a[i] = min(a[i], v);
        for (i >>= 1 ; i ; i >>= 1) {
            a[i] = min(a[i << 1 | 0], a[i << 1 | 1]);
        }
    }
    int prod(int r) const {
        assert(0 <= r and r <= n);
        int res = INF;
        r += n;
        for (int l = n ; l < r ; l >>= 1, r >>= 1) {
            if (l & 1) {
                res = min(res, a[l++]);
            }
            if (r & 1) {
                res = min(res, a[--r]);
            }
        }
        return res;
    }
};
int main() {
    int N;
    cin >> N;
    vector<tuple<int, int, int>> BOX(N);
    vector<int> ws;
    ws.reserve(N);
    for (auto& [h, w, d] : BOX) {
        cin >> h >> w >> d;
		// h <= w <= d になるようにソート
        if (h > w) {
            swap(h, w);
        }
        if (w > d) {
            swap(w, d);
        }
        if (h > w) {
            swap(h, w);
        }
        ws.push_back(w);
    }
	// 箱全体をhの昇順にソート
    ranges::sort(BOX);
	// wを座圧
    ranges::sort(ws);
    ws.erase(unique(ws.begin(), ws.end()), ws.end());
    for (auto& hwd : BOX) {
        get<1>(hwd) = ranges::lower_bound(ws, get<1>(hwd)) - ws.begin();
    }
    SegTree seg(ws.size());
    bool found = false;
    for (int i = 0, j = 0 ; i < N ; i = j) {
		// hが同じ区間[i, j)を得る
        while (j < N and get<0>(BOX[i]) == get<0>(BOX[j])) {
            j++;
        }
        for (int k = i ; k < j ; k++) {
			// 箱kが大きい方として固定して小さい方があるか判定
            int minD = seg.prod(get<1>(BOX[k])); 
            if (minD < get<2>(BOX[k])) {
                found = true;
            }
        }
        for (int k = i ; k < j ; k++) {
			// 箱kのdをデータ構造に登録
            seg.chmin(get<1>(BOX[k]), get<2>(BOX[k]));
        }
    }
    cout << (found ? "Yes\n" : "No\n");
}

</details>

## H: Keep Connect

<details>
<summary>ヒント1</summary>

dpです。(うまいヒントの出し方がわからなかった....)

</details>

<details>
<summary>ヒント2</summary>

現在$2k$頂点のグラフ関して解がわかっている状況から、2頂点後ろに付け加えることを考えます。このとき3つの辺について消すか残すかの8通りの選択肢があります。


</details>

<details>
<summary>ヒント3</summary>

縦の辺によってグラフ全体が初めて連結になる場合があります。dpとして持つ状態として、全体が連結な場合だけを管理するのはダメそうです。

</details>

<details>
<summary>ヒント4</summary>

執筆者の方針では、4状態を持ちました。


</details>

<details>
<summary>実装例</summary>

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <tuple>
#include <ranges>
#include <queue>
#include <atcoder/modint>
using mint = atcoder::modint;
using namespace std;
int main() {
    int N, P;
    cin >> N >> P;
    mint::set_mod(P);
	// 0..連結
	// 1..上側が孤立
	// 2..下側が孤立
	// 3..縦線が一本もない
    vector dp(4, vector<mint>(N));
    dp[0][0] = 1;
    dp[3][1] = 1;
	// 3本の辺の置き方に関する8通りの選択肢
	// 1bit目...上の横辺
	// 2bit目...縦辺
	// 3bit目...下の横辺
    int nxtState[4][8]{
        {-1,2,-1,0,1,0,0,0},
        {-1,-1,-1,-1,-1,1,-1,0},
        {-1,-1,-1,-1,-1,2,-1,0},
        {-1,-1,-1,-1,-1,3,-1,0}
    };
    for (int t = 1 ; t < N ; t++) {
        vector nxt(4, vector<mint>(N));
        for (int i = 0 ; i < 4 ; i++) {
            for (int j = 0 ; j < N ; j++) {
                if (dp[i][j].val() == 0)
                    continue;
                for (int b = 0 ; b < (1 << 3) ; b++) {
                    int eraseEdge = 3 - popcount((unsigned)b);
                    if (j + eraseEdge >= N) {
                        continue;
                    }
                    if (nxtState[i][b] == -1)
                        continue;
                    nxt[nxtState[i][b]][j + eraseEdge] += dp[i][j];
                }
            }
        }
        dp = move(nxt);
    }
    for (int i = 1 ; i < N ; i++) {
        mint ans = dp[0][i];
        cout << ans.val() << (i + 1 == N ? '\n' : ' ');
    }
}

</details>

## I: 最古の遺跡2

<details>
<summary>ヒント1</summary>

俗に凸包dpと呼ばれる典型テクニックを使うだけの問題です。[凸包テク](https://259-momone.hatenablog.com/entry/2021/07/25/025655)とは違うものを指しています。初見の人は実装例を見ると「こんなんでいいのか？！」という気持ちになるかもしれません。それくらい面白いテクニックです。
- Library Checkerにある[Count Points in Triangles](https://judge.yosupo.jp/problem/count_points_in_triangle)の最も有名な応用例の一つです。この問題では使いませんが...

最初から解説や文献を見て良いので、ICPC幾何担当の人はやっておきましょう。

</details>

<details>
<summary>実装例</summary>

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <tuple>
#include <ranges>
#include <queue>
using namespace std;
using Point = pair<int, int>;
Point operator-(Point p, Point q) {
    return {p.first - q.first, p.second - q.second};
}
bool argcomp(Point p, Point q) {
    return p.first * q.second - p.second * q.first > 0;
}
int main() {
    int N;
    cin >> N;
    vector<Point> P(N);
    for (auto& [x, y] : P) {
        cin >> x >> y;
    }
    ranges::sort(P);
    vector<pair<int, int>> vecs;
    for (int i = 0 ; i < N ; i++) {
        for (int j = i + 1 ; j < N ; j++) {
            vecs.push_back({i, j});
        }
    }
    ranges::sort(vecs, [&](auto i, auto j) {
                return argcomp(P[i.second] - P[i.first], P[j.second] - P[j.first]);  
            });
    vector dp(2, vector(N, vector<int>(N, -1)));
    for (int t = 0 ; t < 2 ; t++) {
		// 気持ちとしては、t = 0で下側凸包、t = 1で上側凸包を形成している
        for (int i = 0 ; i < N ; i++) {
            dp[t][i][i] = 1;
        }
        for (auto [from, to] : vecs) {
            for (int st = 0 ; st < N ; st++) {
                if (dp[t][st][from] == -1) {
                    continue;
                }
                dp[t][st][to] = max(dp[t][st][to], dp[t][st][from] + 1);
            }
        }
        ranges::reverse(vecs);
    }
    int ans = 0;
    for (int i = 0 ; i < N ; i++) {
        for (int j = i + 1 ; j < N ; j++) {
            ans = max(ans, dp[0][i][j] + dp[1][i][j] - 2);
        }
    }
    cout << ans << '\n';
}

</details>