ステップ 1

カッコ列の気持ちになってみましょう。まず、文字 0 を (、文字 1 を ) とみなしたとき、最終的な黒板の文字列を正しいカッコ列にすることは \((a_i, b_i)\) の値にかかわらず可能です。なぜなら、各ターンで Alice は \(a_i\) と \(b_i\) のうち大きい方を選択して 1 に書き換えれば良いからです。

同様に、たとえば「文字列を 1, 2, 3, 4, 5, 6 文字目の順に読んだ時に正しいカッコ列にすること」だけでなく、「文字列を 3, 4, 1, 6, 5, 2 文字目の順に読んだ時に正しいカッコ列にすること」のように、文字列を普通ではない順番で読んだときに正しいカッコ列にすることも可能です。

ここで、0 と 1 を \(N\) 個ずつ含む文字列は \({}_{2N}C_{N}\) 個ある一方、長さ \(2N\) の正しいカッコ列は \({}_{2N}C_{N}/(N+1)\) 通りしかありません。したがって、もし Alice の戦略（例は以下）を適切に決めれば、司会者の宣言する文字が \(N+1\) 通りあっても Alice はマジックに成功する可能性があるように見えます。もちろん、本問題の設定の \(N\) 通りであればなおさらです。

戦略の例（イメージ）

• 司会者が A を宣言した場合、1, 2, 3, 4, 5, 6 文字目の順に読んだ時に正しいカッコ列にすることを目指す
• 司会者が B を宣言した場合、3, 4, 1, 6, 5, 2 文字目の順に読んだ時に正しいカッコ列にすることを目指す
• 司会者が C を宣言した場合、5, 3, 6, 1, 2, 4 文字目の順に読んだ時に正しいカッコ列にすることを目指す

しかし、このような戦略が上手くいくには、どのカッコ列も複数の文字に属してはいけません。たとえば上の戦略の場合、カッコ列 ()(())（文字列 010011 に対応）は司会者が A を宣言した場合でも B を宣言した場合でも作られる可能性があるため、上手くいきません。それでは、果たして上手くいく戦略は存在するのでしょうか。

ステップ 2

まずは例として、\(N=4\) の場合を考えてみましょう。実は、以下の戦略が上手くいきます。

• 司会者が A を宣言した場合、文字列を 2, 3, 4, 5, 6, 7, 8, 1 文字目の順に読み、正しいカッコ列を目指す
• 司会者が B を宣言した場合、文字列を 4, 5, 6, 7, 8, 1, 3, 2 文字目の順に読み、正しいカッコ列を目指す
• 司会者が C を宣言した場合、文字列を 6, 7, 8, 1, 5, 2, 3, 4 文字目の順に読み、正しいカッコ列を目指す
• 司会者が D を宣言した場合、文字列を 8, 1, 7, 2, 3, 4, 5, 6 文字目の順に読み、正しいカッコ列を目指す

なぜこれが上手くいくのでしょうか。カッコ列の深さのダイヤグラム（定義は B 問題の解説を参照）を考えた時に、深さが最小となる最初の場所を \(u_l\)、最後の場所を \(u_r\) とします。たとえばカッコ列が )()( の場合は \((u_l, u_r) = (1, 3)\) となります。このとき、以下が成り立つため、どのカッコ列も複数の文字に属さず、すなわち上記の戦略は上手く行きます。\(u_l\) と \(u_r\) の偶奇は同じであることに注意してください。

• A が宣言された場合に生成されるカッコ列の必要十分条件は、\(u_l = 1\) であること
• B が宣言された場合に生成されるカッコ列の必要十分条件は、\(u_l = 3\) または \(u_r = 2\) であること
• C が宣言された場合に生成されるカッコ列の必要十分条件は、\(u_l = 5\) または \(u_r = 4\) であること
• D が宣言された場合に生成されるカッコ列の必要十分条件は、\(u_l = 7\) または \(u_r = 6\) であること

そして一般の \(N\) の場合でも、司会者が \(x\) 番目の英大文字 \((1 \leq x \leq N)\) を宣言した場合に \(2x, 2x+1, \dots, N, 1, 2x-1, 2, 3, \dots, 2x-2\) 文字目の順に読めば、全部上手くいくことが同様に証明できます。したがって、以下の解答例のような実装をすると AC が得られます。

解答例（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Order {
	int ord[20];
};

int main() {
	// step 1. 最初の入力
	int N, T; cin >> N >> T;

	// step 2. どの順にカッコ列を読むかを決める
	vector<Order> read_order(N);
	for (int num = 1; num <= N; num++) {
		Order order;
		for (int i = 0; i < 2 * N; i++) {
			if (i <= 2 * (N - num)) order.ord[i] = 2 * num + i;
			else if (i == 2 * (N - num) + 1) order.ord[i] = 1;
			else if (i == 2 * (N - num) + 2) order.ord[i] = 2 * num - 1;
			else order.ord[i] = i - (2 * (N - num) + 1);
		}
		read_order[num - 1] = order;
	}

	// step 3. 2n_C_n 枚のカードを辞書順にソート
	vector<string> card_sorted;
	for (int i = 0; i < (1 << (2 * N)); i++) {
		string str = "";
		int count_zero = 0; // カード内の 0 の個数を記録（N 個でなければならない）
		for (int j = 0; j < 2 * N; j++) {
			str += ('0' + ((i >> j) & 1));
			if (str[str.size() - 1] == '0') count_zero += 1;
		}
		if (count_zero == N) card_sorted.push_back(str);
	}
	sort(card_sorted.begin(), card_sorted.end());

	// step 4. 最初の出力
	for (string card : card_sorted) {
		int index = -1; // このカードはどの順番に文字を読んだときに正しいカッコ列になるか
		for (int num = 0; num < N; num++) {
			bool valid_order = true;
			int depth = 0;
			for (int i = 0; i < 2 * N; i++) {
				depth += (card[read_order[num].ord[i] - 1] == '0' ? +1 : -1);
				if (depth < 0) valid_order = false;
			}
			if (valid_order == true) index = num;
		}
		if (index == -1) cout << 'A';
		else cout << (char)('A' + index);
	}
	cout << endl;

	// step 5. マジックを始める
	for (int i = 0; i < T; i++) {
		string s; cin >> s;
		vector<int> inverse_order(2 * N + 1, 0);
		for (int j = 0; j < 2 * N; j++) {
			inverse_order[read_order[s[0] - 'A'].ord[j]] = j;
		}
		for (int j = 0; j < N; j++) {
			int a, b; cin >> a >> b;
			cout << (inverse_order[a] > inverse_order[b] ? a : b) << endl;
		}
	}
	return 0;
}