https://codeforces.com/gym/102822/problem/C
A Trie is a tree data structure used to store strings. Here is Little Rabbit's C++ code for inserting and querying a string in a Trie. The character set is lowercase letters.
struct Trie {
int e[N][26], val[N], tot; // N is a constant
Trie() {
tot = 0;
val[0] = Rand(1, 1000000000);
memset(e, 0, sizeof e);
}
void insert(const char *s, int n) { // n is the length of string s
for (int i = 0, u = 0; i < n; u = e[u][s[i] - 'a'], i++)
if (!e[u][s[i] - 'a']) {
e[u][s[i] - 'a'] = ++tot;
val[tot] = Rand(1, 1000000000);
// Rand(l, r) can generate
// distinct random numbers in the range of [l, r]
}
}
int query(const char *s, int n) {
// n is the length of string s
int u = 0;
for (int i = 0; i < n; u = e[u][s[i] - 'a'], i++)
if (!e[u][s[i] - 'a'])
break;
return val[u];
}
};Please note that the integers generated by Rand function are all distinct.
The first line of the input contains an integer T (1≤T≤5000) — the number of test cases.
The first line of each test case contains an integer n (1≤n≤105) — the number of times Little Rabbit uses the query function.
Then in the next n lines, each line contains a string s containing only lowercase letters and an integer v (1≤v≤109), which means Little Rabbit queries the string s, and the return value is v. The sum of the lengths of the strings in each test case will not exceed 105, and the sum of the lengths of the strings in all test cases will not exceed 5×105
For the x-th test case, if the answer is yy, output Case #x: y in a single line. If no Trie can meet the conditions, output Case #x: -1 in a single line.
6
2
aa 1
a 2
1
a 1
3
aa 1
ab 1
ac 1
2
aa 1
ac 2
3
aaa 1
ac 1
aa 3
3
aa 1
ac 1
a 3Case #1: 3
Case #2: 1
Case #3: 1
Case #4: 3
Case #5: -1
Case #6: -1