CF202B Brand New Easy Problem

在一些人中广为人知的白俄罗斯运动程序员 Lesha 决定赚些钱，为买一个大一平方米的公寓。他想在 Torcoder.com 网站举办一场 Super Rated Match（SRM）。但问题来了——严苛的 torcoder 协调员 Ivan 拒绝接受 Lesha 的任何题目，说每一道都是“duped”（即重复的）。一天，他们差点因为 Ivan 又拒收了一道题而争吵起来。 你被邀请作为公正的裁判，判断这道题究竟是不是全新的，或者 Ivan 是否有道理，这道题和以前 SRM 里用过的题有些相似。 你将得到 Lesha 提交的问题描述，以及 Torcoder.com 题库中每道题的描述。每道题的描述是一串单词。保证 Lesha 的题目中没有重复的单词，但题库中的题目描述可能有任意数量的重复单词。 Lesha 的题与某道题库中题目的“相似度”定义如下：在 Lesha 的问题的所有单词排列中，选出一种排列，在题库题目的单词序列中作为子序列出现。如果有多种排列满足条件，选择逆序对数量最少的排列。则“相似度”可以写作 $p = n! - x$，其中 $n$ 为 Lesha 问题中的单词数量，$x$ 为所选排列的逆序对数。注意“相似度” $p$ 总是正整数。 如果 Ivan 的题库中没有一道题包含 Lesha 问题单词某种排列作为子序列，则称 Lesha 的问题是全新的。 请你帮忙判断 Lesha 的题是否全新；如果不是，请指出题库中与 Lesha 的问题最相似的那道题。

第一行包含一个整数 $n$（$1 \leq n \leq 4$），表示 Lesha 的问题中单词个数。第二行包含 $n$ 个用空格分隔的单词，表示问题的简要描述。 第三行包含一个整数 $m$（$1 \leq m \leq 10$），表示 Torcoder.com 题库中的题目数。接下来 $m$ 行，每行格式为“$k\ s_1\ s_2\ ...\ s_k$”，其中 $k$（$1 \leq k \leq 20$）为该题目包含的单词数，$s_i$ 为该题描述中的第 $i$ 个单词。 所有描述中的单词均只包含不超过 $10$ 个小写英文字母。

如果 Lesha 的问题是全新的，输出字符串“Brand new problem!”（不含引号）。 否则，第一行输出与 Lesha 的问题最相似的题库题目的编号（从 1 开始，按照输入顺序编号）。如果有多题相似度相同，输出编号最小的。第二行输出一个字符串，格式为 \[:, 后接 $p$ 个字符 |，最后是 :\]，$p$ 为相似度。

提醒一下，逆序对的数量指排列中有多少对单词不按原顺序出现。例如，原描述为“add two numbers”，排列“numbers add two”包含两个逆序对，即“numbers”与“add”，“numbers”与“two”。 序列 $b_1,b_2,\dots,b_k$ 是序列 $a_1,a_2,\dots,a_n$ 的子序列，指存在下标 $1 \leq i_1 < i_2 < \dots < i_k \leq n$，使得 $a_{i_j}=b_j$（换句话说，$b$ 可以由 $a$ 删去若干元素所得）。 在第一个样例中，第一个题目包含“find the palindrome next”这一排列作为子序列，且逆序对数为 1（“palindrome”与“next”）。 在第二个样例中，没有题目包含某种排列作为 Lesha 问题单词的子序列。 由 ChatGPT 5 翻译