W2: Quy hoạch thành phố IONAH

Bài toán quy hoạch thành phố IONAH

Tại thành phố IONAH có D quận, được đánh số từ 1 đến D. Chủ tịch thành phố muốn xây dựng các tuyến đường một chiều để sinh viên học ở các trường đại học ở Quận 1 có thể đi đến lớp học lập trình của Deverion ở quận D được thuận tiện. Giữa các quận có thể có một đường 1 chiều hoặc không có đường nào. Và không có đường nào xuất phát từ quận D cả (Vì sinh viên đã đến đây học là cuốn luôn rồi).

Để kỷ niệm M năm thành lập thành phố. Chủ tịch muốn các tuyến đường một chiều được xây dựng để đảm bảo có đúng M và chỉ M cách đi từ Quận 1 đến Quận D

Bạn hãy giúp Chủ tịch thành phố lên phương án quy hoạch cho bài toán đó nhé?

Input

Dòng đầu tiên là số bài test trong file - T. T dòng tiếp theo, mỗi dòng gồm hai số DM

Output

Với mỗi bài test, ghi ra một dòng gồm Case #x: y, trong đó x là thứ tự bài test tính từ 1 và yPOSSIBLE hoặc IMPOSSIBLE thể hiện có thể tìm được phương án quy hoạch phù hợp với mong muốn của Chủ tịch thành phố hay không. Trong trường hợp nếu có, B dòng tiếp theo sẽ gồm B ký tự thể hiện ma trận quy hoạch thoả mãn đề bài. Số thứ j ở dòng i1 nếu có đường một chiều xuất phát từ Quận i đến Quận j và ngược lại (i, j tính từ 1). Nếu không có đường thì giá trị mặc định sẽ là 0. Trong trường hợp có nhiều phương án quy hoạch, bạn chỉ cần in ra một phương án bất kỳ.

Limits

Thời gian: 20 giây / bài test
Bộ nhớ: 1 GB.
1 ≤ T ≤ 100.

Giới hạn

2 ≤ D ≤ 6.
1 ≤ M ≤ 20.

Nâng cao (phần dành cho các bạn thích thử thách)

2 ≤ D ≤ 50.
1 ≤ M ≤ 1018

Ví dụ

Input
3
5 4
2 1
4 20

Output
Case #1: POSSIBLE
01001
00110
00001
00101
00000
Case #2: POSSIBLE
01 00
Case #3: IMPOSSIBLE

Ví dụ ở trên là một phương án quy hoạch thoả mãn điều kiện, có thể có những phương án khác thoả mãn.
Sơ đồ thiết kế cho Case 1 như sau

slides_case1

Có 4 cách để đi từ Quận 1 đến Quận 5:

  • 1 đi đến 5
  • 1 đi đến 2 đi đến 3 đi đến 5
  • 1 đi đến 2 đi đến 4 đi đến 5
  • 1 đi đến 2 đi đến 4 đi đến 3 đi đến 5