철도

사이가 나쁜 A, B 두 나라가 있다. A나라는 B나라를 침략하기 위해 B나라의 철도망을 알아내려 한다. B나라에 여러 차례 스파이를 보냈지만 항상 의미있는 정보를 캐기 전 잡혔기 때문에, A나라가 알고 있는 정보는 다음이 전부이다. 

• B나라의 철도망은 모두 $N$개의 역으로 이루어져 있고, 각 역은 $1$부터 $N$까지 번호가 붙어 있다.
• 서로 다른 어떤 두 역을 고르더라도 직접 철로로 이어져 있거나, 철로로 이어진 다른 역(들)을 통해서 이어져 있다. 
• 어떤 두 역을 고르더라도 이 둘을 연결하는 경로는 정확히 하나이다.
• 자신과 자신을 철로로 직접 이은 경우는 없다. 

스파이를 보내는 것은 한계가 있음을 깨닫고, A나라는 B나라 철도회사 고위 간부를 매수하여 철도망을 그린 그림을 얻어내려고 한다. 이 그림을 직접 보내면 배신자가 누구인지 알려질 것이므로, 배신자는 다음과 같이 그림을 고쳐서 A나라에 보낼 것이다.

• 철도망을 그린 그림 위에 $K$개의 가짜 철로를 그린다. 즉, 그림에서 철로로 직접 연결되지 않은 서로 다른 두 역 $a$와 $b$를 골라서, 이 둘을 가짜 철로로 직접 잇는다. 이를 $K$번 반복한다.
• 하나의 역에 특별한 표시를 한다.
• 마지막으로, 역들의 번호를 모두 지운다. 

배신자는 최종적으로 얻은 그림을 A나라에 전송한다. 이 정보만으로는 B나라의 철도망을 그린 그림이라는 것을 알기 어렵기 때문에, 비밀 정보가 유출되었다는 사실을 아무도 모를 것이다.   

이 계획이 성공하기 위해서는 다음과 같은 문제가 해결되어야 한다. 

• A나라가 받은 그림에는 역들의 번호가 지워져 있고, 또한 어느 철로가 진짜이고 가짜인지 표시되어 있지 않다. 알 수 있는 것은 어느 역에 특별한 표시가 되어 있는지, 그리고 가짜 철로를 총 $K$군데 놓았다는 사실뿐이다.  
• 따라서, 보내는 쪽에서는 받는 쪽이 그림만 보고 어느 철로가 진짜이고 어느 철로가 가짜인지 알 수 있도록 적절한 위치에 가짜 철로를 놓고, 적절한 역에 특별한 표시를 해야 한다.
• 또한 받는 쪽에서는 보내는 쪽이 그림을 고친 방법을 이해하고, 받은 그림에서 원래 철도망을 그린 그림을 
• 구해야 한다.

위에서 설명한 것처럼, 철도망을 그린 그림을 고치는 함수와, 이 그림으로부터 진짜 철도망을 구하는 함수 둘이 필요하다. A나라는 여러분에게 이 일을 맡기려고 한다.

• $1 \le T \le 200$
• $3 \le N \le 200$ 
• $1 \le K < \frac{N}{2}$