# **[2021/01/19 TPC](https://codeforces.com/group/9f55GySeDA/contest/312924)**
# **A. Hongcow Learns the Cyclic Shift**

問題文通りにシフトを全探索して, setで管理するだけ.

set<string> T;
string S;
cin >> S;
rep(i, len(S)) {
    T.insert(S);
    S = S.substr(1, len(S) - 1) + S[0];
}
cout << len(T) << rt;

# **B. Hongcow Solves A Puzzle**

ごちゃごちゃ書いてあるけど結局長方形かどうか判定するだけ.

ll N, M, l = INF, r = -1, u = -1, d = INF;
cin >> N >> M;
string S[N];
rep(i, N) cin >> S[i];
rep(i, N) rep(j, M) {
    if (S[i][j] == 'X') {
        chmin(d, i);
        chmax(u, i);
        chmin(l, j);
        chmax(r, j);
    }
}
inc(i, d, u) inc(j, l, r) if (S[i][j] != 'X') return puts("NO") & 0;
puts("YES");

# **C. Hongcow Builds A Nation**

連結成分をクリークにするだけ. 浮いている頂点は一番大きいところにまとめる.

ll N, M, K, A, B;
cin >> N >> M >> K;
ll C[K];
UFS uf(N);
rep(i, K) cin >> C[i], C[i]--;
rep(i, M) cin >> A >> B, uf.unite(A - 1, B - 1);
ll res = 0, used[N], mx = -1, cnt = 0;
rep(i, N) used[i] = 0;
rep(i, K) {
    chmax(mx, uf.size(C[i]));
    res += uf.size(C[i]) * (uf.size(C[i]) - 1) / 2;
    used[uf.root(C[i])] = 1;
}
rep(i, N) if (used[uf.root(i)] != 1) cnt++;
cout << res + (mx + cnt) * (mx + cnt - 1) / 2 - mx * (mx - 1) / 2 - M << rt;

# **D. Hongcow's Game**

パズルゲー. $2^k$ の縦格子を作ると, いい感じに exclude j を計算できる.

ll N;
cin >> N;

ll res1[10][1000], res2[10][1000], pw[10];
rep(i, 10) pw[i] = pow(2, i);
rep(i, 10) rep(j, N) res1[i][j] = res2[i][j] = INF;
vector<ll> A[10], B[10];
rep(i, 10) {
	rep(j, N) {
        if (j % (pw[i] * 2) < pw[i]) {
            A[i].pb(j + 1);
        } else {
            B[i].pb(j + 1);
        }
    }

    if (len(A[i])) {
        cout << len(A[i]) << endl;
    rep(j, len(A[i])) {
        cout << A[i][j];
        if (j == len(A[i]) - 1) cout << endl;
        else
            cout << sp;
        }
        rep(j, N) cin >> res1[i][j];
    }

    if (len(B[i])) {
    cout << len(B[i]) << endl;
    rep(j, len(B[i])) {
        cout << B[i][j];
        if (j == len(B[i]) - 1) cout << endl;
        else
        	cout << sp;
    }
    	rep(j, N) cin >> res2[i][j];
    }
}

ll res[N];
rep(i, N) res[i] = INF;
rep(i, N) {
	rep(j, 10) {
        ll f = 1;
        each(k, A[j]) if (k == i + 1) f = 0;
        if (f) chmin(res[i], res1[j][i]);
    }
    rep(j, 10) {
        ll f = 1;
        each(k, B[j]) if (k == i + 1) f = 0;
        if (f) chmin(res[i], res2[j][i]);
    }
}
cout << -1 << rt;
rep(i, N) {
    cout << res[i];
    if (i == N - 1) cout << endl;
    else
    	cout << sp;
}

# **E. Hongcow Buys a Deck of Cards**

BitDPできそうな形をしているが, よく見ると $10^7$ オーダーのコストをキーに持たないといけない. 或いはうまく半分前列挙できればそこそこ速いがそれでも定数倍の重い $10^9$ 程度の計算回数になってしまう. (ここまでコンテスト中の考察, 以降検索して出てきた中国語の解説ページを読んで) よく見ると, コストの改善分をキーにするとこれが $O(n^2)$ で全体で $O(2^nn^3)$ になり間に合う.