#include <stdio.h>
#include <string.h>

int h[10005][2];
int n, m;
int link[10005];
int b[10005];

int dfs(int u)
{
	int i, v;

	for (i = 0; i < 2; i++)
	{
		v = h[u][i];
		if (!b[v])
		{
			b[v] = 1;
			if (link[v] == -1 || dfs(link[v]))
			{
				link[v] = u;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	int cas;
	int i;

	scanf("%d",  &cas);
	while (cas-- > 0)
	{
		scanf("%d%d", &m, &n);
		memset(link, -1, sizeof(int) * (n + 1));
		for (i = 0; i < m; i++)
		{
			scanf("%d%d", &h[i][0], &h[i][1]);
		}
		for (i = 0; i < m; i++)
		{
			memset(b, 0, sizeof(int) * (n + 1));
			if (!dfs(i))
			{
				break;
			}
		}
		puts(i == m ? "successful hashing" : "rehash necessary");
	}
	return 0;
}