Description

给定一个n个点，m条边的强连通有向图。请保留其中恰好2n条边，使得它还是强连通的。

Format

Input

第一行包含一个正整数T，表示测试数据的组数。

每组数据第一行包含两个正整数n,m(n>=4,m>2n)，表示点数和边数。

接下来m行，每行两个正整数x,y(1<=x,y<=n,x!=y)，表示一条x到y的单向边。

数据保证图强连通，且不存在重边

sum(n),sum(m)<=100000。

Output

对于每组数据，输出m-2n行

每行描述一条要被删除的边，和输入格式一样，有多解输出任意一组。

Samples

1
4 9
1 2
1 3
2 3
2 4
3 2
3 4
4 1
4 2
4 3

1 3

Source 鸣谢Claris提供翻译及SPJ