Woburn Challenge 2017-18 Round 3 - Senior Division

The social network Google+ has ~N~ ~(2 \le N \le 6)~ users, with user IDs from ~1~ to ~N~. Each pair of distinct users are either friends with one another, or not.

You're given an ~N \times N~ grid of values ~M~, with ~M_{i,j}~ ~(0 \le M_{i,j} \le N)~ being the number of mutual friends which users ~i~ and ~j~ have in common. This corresponds to the number of other users who are friends with both ~i~ and ~j~. Note that it does not depend on whether or not ~i~ and ~j~ are friends with one another. ~M_{i,j} = M_{j,i}~ for each pair of users ~i~ and ~j~, ~M_{i,i}~ is considered to be ~0~ for each user ~i~.

Given the above information, you'd like to guess which users are friends with one another. If there exists a valid set of friendships which result in the given grid of mutual friend counts, then please output the number of friendships ~F~, followed by ~F~ lines each describing one of the friendships (with ~2~ integers, the IDs of the two users involved in the friendship). No two friendships should involve the same unordered pair of users. If there are multiple valid sets of friendships, you may output any of them. If there are no valid sets of friendships, output Impossible instead.

Subtasks

In test cases worth ~4/13~ of the points, ~N \le 3~.

Input Specification

The first line of input consists of a single integer, ~N~.
~N~ lines follow, the ~i~-th of which consists of integers, ~M_{i, 1 \dots N}~, for ~i = 1 \dots N~.

Output Specification

Either the string Impossible, or ~1~ integer ~F~ followed by ~F~ lines, the ~i~-th of which contains ~2~ integers describing the ~i~-th friendship.

Sample Input 1

5
0 0 0 1 2
0 0 2 0 0
0 2 0 0 0
1 0 0 0 1
2 0 0 1 0

Sample Output 1

5
1 2
2 5
5 3
3 1
2 4

Sample Input 2

3
0 1 1
1 0 0
1 0 0

Sample Output 2

Impossible

Sample Explanations

In the first case, one valid set of ~5~ friendships is indicated in the sample output. For this set, users ~1~ and ~5~ have exactly ~2~ mutual friends (users ~2~ and ~3~) as required, users ~1~ and ~4~ have exactly ~1~ mutual friend (user ~2~) as required, and so on. Note that there exist other outputs which would also be accepted. For example, the friendship between users ~2~ and ~4~ could be replaced with a friendship between users ~3~ and ~4~, the friendships could be outputted in any order, and the users in each friendship could be swapped.

In the second case, no set of friendships amongst ~3~ users would result in the required grid of mutual friend counts.