수색 작전

바이트란트에는 $n$개의 도시가 있고, 이 도시들은 $m$개의 양방향 도로로 연결되어 있다. 그런데 이 도로는 선량한 시민뿐 아니라 어떤 위험한 범죄자에게도 이용되고 있다.

얼마 전부터 바이트란트에서는 이 범죄자를 붙잡아 법의 심판대에 세우기 위한 대수색이 벌어지고 있다. 그러나 아직까지 그 악당은 자유를 누리고 있다. 그는 낮 동안에는 도시 하나에 숨어 지내고, 밤이 되면 $m$개의 도로 중 하나를 따라 몰래 이웃 도시로 이동한다. 그는 결코 이틀 연속으로 같은 도시에 머무르지 않는다.

현재 그의 위치에 대해서는 아무것도 알려져 있지 않다. 이때 산전수전 다 겪은 바이테비치 중위가 수색에 나선다. 그는 하루에 도시 한 곳을 샅샅이 뒤질 수 있으며, 범죄자가 바로 그 도시에 있다면 어렵지 않게 붙잡는다. 또한 밤에는 헬리콥터를 이용해 다른 어떤 도시로든 이동할 수 있다. 문제는 범죄자가 중위가 며칠째에 어느 도시를 뒤질지 미리 정확히 알고 있다는 점이며, 그래서 그는 가능한 한 오랫동안 중위를 따돌리기로 마음먹었다.

바이테비치 중위가 범죄자를 붙잡을 가망이 있는가? 더 정확히 말하면, 범죄자를 반드시 붙잡을 수 있는 중위의 전략이 존재하는가? 만약 존재한다면, 그것을 이루기까지 최소 며칠이 필요한가?

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \le t \le 15$)가 주어지며, 각 테스트 케이스는 그다음에 차례대로 주어진다.

한 테스트 케이스의 설명은 도시의 수와 도시를 잇는 도로의 수를 나타내는 두 정수 $n$과 $m$ ($1 \le n \le 75\,000$, $0 \le m \le 75\,000$)으로 시작한다. 도시에는 $1$번부터 $n$번까지 번호가 매겨져 있다. 이어지는 $m$개의 줄에는 각각 두 정수 $a_i$와 $b_i$ ($1 \le a_i < b_i \le n$)가 주어지며, 이는 도시 $a_i$와 $b_i$가 양방향 도로로 연결되어 있음을 뜻한다. 어떤 두 도시도 두 개를 넘는 직접 도로로 연결되어 있지 않으며, 도로망을 통해 어느 도시에서든 다른 모든 도시로 갈 수 있다.

각 테스트 케이스에 대해, 출력의 첫 줄에는 범죄자를 붙잡을 수 있는 전략이 존재하면 TAK를, 그렇지 않으면 NIE를 출력한다. 둘째 줄에는 정확히 하나의 정수를 출력한다. 전략이 존재한다면 이 정수는, 범죄자가 중위의 움직임을 미리 알고 있다고 가정할 때 중위가 범죄자를 붙잡는 데 필요한 최소 날짜 수여야 한다. 그렇지 않다면 둘째 줄에는 $-1$을 출력한다.

예제의 셋째 테스트 케이스에 대한 설명: 중위는 도시를 $2$, $4$, $4$, $2$번 순서로 뒤지면 된다. 그러면 범죄자는 달아날 방법이 없다.