# Cuckoo Hashing

A stronger variant is Cuckoo Hashing^{1}. The
idea is to use two hash functions $h_1$ and $h_2$. Thus each string maps to two
positions in the table. A query string $q$ is now handled as follows: you
compute both $h_1(q)$ and
$h_2(q)$, and if
$T[h_1(q)]=q$, *or*
$T[h_2(q)]=q$, you
conclude that $q$ is in
${D}$. The name “Cuckoo
Hashing” stems from the process of creating the table.
Initially you have an empty table. You iterate over the words
$d$ in ${D}$, and insert them one by one. If
$T[h_1(d)]$ is free, you
set $T[h_1(d)]=d$.
Otherwise if $T[h_2(d)]$
is free, you set $T[h_2(d)]=d$. If both are occupied
however, just like the cuckoo with other birds’ eggs, you evict
the word $r$ in
$T[h_1(d)]$ and set
$T[h_1(d)]=d$. Next you
put $r$ back into the
table in its alternative place (and if that entry was already
occupied you evict that word and move it to its alternative
place, and so on). Of course, we may end up in an infinite loop
here, in which case we need to rebuild the table with other
choices of hash functions. The good news is that this will not
happen with great probability even if ${D}$ contains up to $n/2$ words!

## Input

On the first line of input is a single positive integer $1\leq t \leq 50$ specifying the number of test cases to follow. Each test case begins with two positive integers $1 \leq m \leq n \leq 10000$ on a line of itself, $m$ telling the number of words in the dictionary and $n$ the size of the hash table in the test case. Next follow $m$ lines of which the $i$:th describes the $i$:th word $d_ i$ in the dictionary ${D}$ by two non-negative integers $h_1(d_ i)$ and $h_2(d_ i)$ less than $n$ giving the two hash function values of the word $d_ i$. The two values may be identical.

## Output

For each test case there should be exactly one line of
output either containing the string “`successful hashing`” if it is possible to insert
all words in the given order into the table, or the string
“`rehash necessary`” if it is
impossible.

Sample Input 1 | Sample Output 1 |
---|---|

2 3 3 0 1 1 2 2 0 5 6 2 3 3 1 1 2 5 1 2 5 |
successful hashing rehash necessary |

**Footnotes**

- Cuckoo Hashing was suggested by the danes R. Pagh and F. F. Rödler in 2001