407522: GYM102822 C Code a Trie
Description
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[s[i] - 'a'], i++)
if (!e[s[i] - 'a']) {
e[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[s[i] - 'a'], i++)
if (!e[s[i] - 'a'])
break;
return val;
}
};
Please note that the integers generated by $$$Rand$$$ function are all distinct.
Little Rabbit inserts some (possibly zero) strings in the Trie by using the $$$insert$$$ function. But after a while, he totally forgets those strings he has inserted. So he uses the $$$query$$$ function $$$n$$$ times to query some strings and gets $$$n$$$ return values. According to these values, you need to tell Little Rabbit how many nodes the Trie has at least. Please note that the root of the Trie should also be counted as a node. In the code above, the number of nodes is $$$\text{tot}+1$$$.
InputThe first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 5000$$$) — the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — 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 \le v \le 10^9$$$), 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 $$$10^5$$$, and the sum of the lengths of the strings in all test cases will not exceed $$$5 \times 10^5$$$
OutputFor the $$$x$$$-th test case, if the answer is $$$y$$$, output $$$Case$$$ #$$$x$$$: $$$y$$$ in a single line. If no Trie can meet the conditions, output $$$Case$$$ #$$$x$$$: -$$$1$$$ in a single line.
ExampleInput6 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 3Output
Case #1: 3 Case #2: 1 Case #3: 1 Case #4: 3 Case #5: -1 Case #6: -1