## WC '17 Contest 3 S1 - Mutual Friends

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
##### Woburn Challenge 2017-18 Round 3 - Senior Division

The social network Google+ has users, with user IDs from to . Each pair of distinct users are either friends with one another, or not.

You're given an grid of values , with being the number of mutual friends which users and have in common. This corresponds to the number of other users who are friends with both and . Note that it does not depend on whether or not and are friends with one another. for each pair of users and , is considered to be for each user .

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 , followed by lines each describing one of the friendships (with 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.

In test cases worth of the points, .

#### Input Specification

The first line of input consists of a single integer, .
lines follow, the -th of which consists of integers, , for .

#### Output Specification

Either the string Impossible, or integer followed by lines, the -th of which contains integers describing the -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 friendships is indicated in the sample output. For this set, users and have exactly mutual friends (users and ) as required, users and have exactly mutual friend (user ) as required, and so on. Note that there exist other outputs which would also be accepted. For example, the friendship between users and could be replaced with a friendship between users and , 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 users would result in the required grid of mutual friend counts.