K. Efficient Interception
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The Kingdom of Berland is great and glorious, but it is currently ruled by a powerful and peevish king Vlad who got old and now sees treasons and plots all around him. He now suspects his two sons in planning a coup, so he decided to establish his control over all their communications.

The Kingdom of Berland is formed by $$$n$$$ cities connected by $$$m$$$ bidirectional roads in a way that makes it possible to get from any city to any other city using these roads only. The elder son of King Vlad lives in city $$$1$$$, while the younger son lives in city $$$n$$$.

In order to control all messengers who run between city $$$1$$$ and city $$$n$$$ Vlad wants to pick some cities and establish a secret police department in each of them. It turns out that no matter how powerful you are, you are not able to keep all the things secret. If city $$$v$$$ has a police department established in it, the mayor of this city somehow becomes aware of this. Moreover, the mayor of any city that is connected to $$$v$$$ by a direct road becomes aware of this police departments as well.

Of course, the King wants to keep his sons unaware of his new secret police. Therefore he has three limitations.

  1. There should be no way to get from city $$$1$$$ to city $$$n$$$ using roads without visiting any city that has a police department in it.
  2. There can be no secret police department in city $$$1$$$ and city $$$n$$$. Though, there can be a secret police department in a city that is connected to city $$$1$$$ or city $$$n$$$ by a direct road.
  3. The total number of city mayors that are aware of at least one secret police department should be minimum possible.

You don't want to help King Vlad in his malicious games, but the problem itself looks nice so you want to find the optimal answer just for fun.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

Then follow $$$t$$$ test cases' descriptions. Each test case description starts with two integers $$$n$$$ and $$$m$$$ ($$$3 \leq n \leq 300$$$, $$$2 \leq m \leq \frac{n \cdot (n - 1)}{2} - 1$$$) — the number of cities and the number of roads in the kingdom of Berland. Each of the following $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$), providing the indices of the cities connected by the $$$i$$$-th bidirectional road.

It is guaranteed that the sum of values of $$$n$$$ in all $$$t$$$ test cases doesn't exceed $$$300$$$.

For each test it is guaranteed that each road connects two distinct cities, no two roads connect the same pair of cities and no road connects city $$$1$$$ with city $$$n$$$.

Output

For each of $$$t$$$ tests print two lines. The first line of the output should contain two integers $$$a$$$ and $$$k$$$, where $$$a$$$ is the answer, i.e. the minimum possible number of city mayors to be aware about at least one secret police department, and $$$k$$$ is the number of secret police departments to be establish in order to achieve answer $$$a$$$. The next line should contain $$$k$$$ distinct indices $$$x_1, x_2, \ldots, x_k$$$ ($$$1 \lt x_i \lt n$$$), providing where exactly to place these secret police departments in the optimal answer. If there are several optimal answers, print any of them.

Example
Input
3
3 2
1 2
2 3
4 4
1 2
2 4
1 3
3 4
13 18
1 2
1 3
1 4
2 5
3 5
3 6
4 6
5 7
6 7
7 8
7 9
8 12
8 11
9 11
9 10
12 13
11 13
10 13
Output
3 1
2 
4 2
2 3 
5 1
7