34514번 - FFT 스페셜 저지

문제

트리의 각 정점은 F 혹은 T 상태를 가진다.

트리에서 길이가 2ドル$인 단순 경로 중 경로 순서대로 정점 상태가 F, F, T면 FFT 경로라 부른다.

FFT 경로의 개수가 정확히 $K$개인 트리 중에서 정점의 개수가 가장 적은 트리를 출력해 보자.

입력

총 $T$개의 테스트 케이스가 입력으로 주어지며, 첫 번째 줄에 $T$가 주어진다.

그다음 줄부터 각 테스트 케이스마다 하나의 줄에 정수 $K$가 주어진다.

출력

각 테스트 케이스마다 주어진 순서대로 다음과 같이 출력한다.

• 첫 번째 줄에 정점의 개수 $N$을 출력한다.
• 두 번째 줄에 길이가 $N$인 문자열 $S$를 출력한다. 문자열 $S$는 F 혹은 T로만 구성된 문자열이다. 문자열 $S$의 $i$번째 문자는 $i$번째 정점의 상태를 의미한다.
• 그다음 줄부터 $N - 1$개의 줄에 걸쳐 조건을 만족하는 트리의 간선 정보를 출력한다. 그중 $i$번째 줄은 양의 정수 $u_i,ドル $v_i$를 공백으로 구분하여 출력한다. 이는 트리의 $u_i$번 정점과 $v_i$번 정점을 잇는 간선이 존재한다는 의미이다. $(1 \le i \le N - 1)$
• 가능한 트리가 여러 개라면 그중 아무것이나 출력한다.

제한

• 1ドル \le T \le 1,000円$
• 1ドル \le K \le 1,000円,000円$
• 1ドル \le u_i, v_i \le N$

힌트