Cho một đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Các đỉnh được đánh số từ \(1\) đến \(n\) và các cạnh được đánh số từ \(1\) đến \(m\). Cạnh thứ \(i\) nối hai đỉnh \(u_{i}\) và \(v_{i}\).

Bạn cần định chiều đồ thị này để biến từ đồ thị vô hướng thành đồ thị có hướng. Nói cách khác, với cạnh thứ \(i\) trong số \(m\) cạnh của đồ thị được cho, bạn cần biến nó thành cung có hướng \(u_{i} \rightarrow v_{i}\) hoặc cung có hướng \(v_{i} \rightarrow u_{i}\).

Sau khi định chiều, bạn muốn số cặp đỉnh \((x, y)\) thoả mãn \(1 \leq x, y \leq n, \sqrt{\dfrac{x^{2} + y^{2}}{2}} > \dfrac{2}{\dfrac{1}{x} + \dfrac{1}{y}}\) và trên đồ thị có đường đi từ \(x\) đến \(y\) là lớn nhất. Lưu ý rằng \((x, y)\) và \((y, x)\) được tính là hai cặp khác nhau, và việc có đường đi từ \(x\) đến \(y\) không đảm bảo rằng sẽ có đường đi từ \(y\) đến \(x\).

Hãy tìm số cặp đỉnh \((x, y)\) thoả mãn điều kiện trên lớn nhất có thể và chỉ ra một cách định chiều cho ra số cặp này.

Input

• Dòng đầu tiên chứa hai số nguyên \(\theta\) và \(\tau\) lần lượt là số thứ tự của subtask chứa test này và số bộ dữ liệu có trong file dữ liệu. Sau đó, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:
  • Dòng đầu tiên là một dòng trống.
  • Dòng thứ hai chứa hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 80000, 1 \leq m \leq 350000)\) lần lượt là số đỉnh và số cạnh của đồ thị.
  • Trong \(m\) dòng còn lại, dòng thứ \(i\) chứa hai số nguyên \(u_{i}\) và \(v_{i}\) \((1 \leq u_{i}, v_{i} \leq n)\) là hai đỉnh được nối bởi cạnh thứ \(i\).
• Gọi \(N\) là tổng giá trị của \(n\) trong tất cả các bộ dữ liệu và \(M\) là tổng giá trị của \(m\) trong tất cả các bộ dữ liệu, dữ liệu vào đảm bảo \(N \leq 24 \times 10^{4}\) và \(M \leq 105 \times 10^{4}\).

Output

• Với mỗi bộ dữ liệu, ghi ra kết quả trên một dòng gồm số nguyên \(k\) \((0 \leq k \leq n \times (n − 1))\) thể hiện số cặp đỉnh \((x, y)\) tối đa thoả mãn điều kiện ở trên; theo sau là xâu ký tự \(s\) chứa chính xác \(m\) ký tự F hoặc B thể hiện một phương án định chiều. Ký tự thứ \(i\) của xâu \(s\) là F cho biết bạn sẽ định chiều cạnh thứ \(i\) theo hướng \(u_{i} \rightarrow v_{i}\); ngược lại, nếu bạn định chiều cạnh thứ \(i\) theo hướng \(v_{i} \rightarrow u_{i}\), ký tự thứ \(i\) của xâu \(s\) là B.
• Nếu có nhiều phương án định chiều tối ưu, bạn được phép in ra một phương án bất kỳ.

Score

Với mỗi test, bạn được \(0\) điểm nếu file kết quả vi phạm ít nhất một trong các điều sau:

• Có dòng khác rỗng ngoại trừ \(\tau\) dòng đầu tiên.
• Có ít nhất một trong \(\tau\) dòng đầu tiên không có dạng \(k\) \(s\).
• Có ít nhất một giá trị \(k\) không thuộc đoạn \([0, n \times (n − 1)]\).
• Có ít nhất một xâu \(s\) có độ dài khác \(m\) hoặc chứa ký tự không phải F hay B.

Ngược lại, gọi \(\rho\) là số bộ dữ liệu bạn cho ra chính xác số cặp đỉnh tối đa và đưa ra một phương án định chiều chính xác, \(\epsilon\) là số bộ dữ liệu bạn cho ra chính xác số cặp đỉnh tối đa nhưng chưa có phương án định chiều chính xác, và \(\Omega\) là số điểm tối đa của test; điểm số của bạn trong test được tính bởi công thức:
\(\left(\left(\dfrac{\rho + \epsilon}{\tau}\right)^{\pi} + \left(\dfrac{\rho}{\tau}\right)^{\epsilon}\right) \times \dfrac{\Omega}{2}\)

Điểm của bài là tổng điểm đạt được trong tất cả các test. Điểm tối đa của mỗi test là như nhau. Điểm tối đa của bài là \(60\).

Scoring

• Subtask \(1\) (\(11\) điểm): \(m \leq 16\) và \(M \leq 48\).
• Subtask \(2\) (\(12\) điểm): Trong đồ thị ban đầu, mỗi đỉnh kề với tối đa hai đỉnh khác.
• Subtask \(3\) (\(13\) điểm): \(m = n − 1\) và \(1 \leq u_{i} < v_{i} = i + 1 \forall 1 \leq i \leq m\).
• Subtask \(4\) (\(14\) điểm): \(n \leq 5000\) và \(N \leq 15000\).
• Subtask \(5\) (\(10\) điểm): Không có ràng buộc gì thêm.

Example

1 2

4 4
1 2
2 3
1 3
1 4

4 3
1 2
3 2
3 4

9 FFBB
6 FBF