주어진 무향 그래프에서 최소 정점 커버(minimum vertex cover)를 찾아라. 재미있지 않은가?

최대 매칭(maximum matching)의 크기를 $M$, 최소 정점 커버의 크기를 $C$라고 하자. 만약 최소 정점 커버가 $smol$하다면, 즉 $C \le M + 1$을 만족한다면, 이를 찾아라.

입력

각 테스트 케이스는 여러 개의 테스트 케이스를 포함한다. 첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 10^4$)가 주어진다.

각 테스트 케이스에 대한 설명이 이어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 $n$과 $m$ ($1 \le n \le 500$, $0 \le m \le \frac{n(n-1)}{2}$)이 주어지며, 이는 그래프의 정점 개수와 간선 개수를 의미한다.

다음 $m$개의 줄에는 그래프의 간선을 설명하며, 각 줄에는 두 정수 $u$와 $v$ ($1 \le u < v \le n$)가 주어진다. 이는 정점 $u$와 $v$가 간선으로 연결되어 있음을 의미한다. 정점은 $1$부터 $n$까지 번호가 매겨져 있다.

그래프는 다중 간선을 포함하지 않음이 보장된다.

모든 테스트 케이스에 대한 $n^2$의 합은 $250\,000$을 넘지 않음이 보장된다.

출력

각 테스트 케이스에 대해, 최소 정점 커버가 $smol$하다면 첫 번째 줄에 그 크기 $C$를 출력하고, 두 번째 줄에 정점 커버를 구성하는 $C$개의 서로 다른 정점을 공백으로 구분하여 출력한다. 그렇지 않은 경우, 한 줄에 "not smol"을 출력한다 (따옴표 제외).

가능한 $smol$ 최소 정점 커버가 여러 개라면, 그중 아무거나 하나를 출력한다.

예제

입력 1

1
5 5
1 2
2 3
3 4
4 5
1 5

출력 1

3
2 3 5

입력 2

2
3 0
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

출력 2

0
not smol

참고

정점 커버(vertex cover)는 모든 간선의 적어도 한쪽 끝점이 집합에 포함되도록 하는 정점들의 집합이다.

매칭(matching)은 어떤 두 간선도 공통된 끝점을 가지지 않는 간선들의 집합이다.

최소 정점 커버라 하더라도 $smol$하지 않으면 정답으로 인정되지 않음에 유의하라.