Submit Best Submissions All Submissions

481. WUZZUF Connections


Problem Statement:
WUZZUF is introducing a new feature called WUZZUF connections, where you will have connections between other WUZZUF users, you simply send a connection request to another user and they either accept or reject it. There's also a feature to block another user, when a user blocks another users, it's as if each of them doesn't exist to the other one.

Part of this feature, is to display the connection degree in each profile of another user you open. The connection degree is simply the minimum number of direct connections you need to go through from yourself to reach that user (can't go through a blocked user).

For example consider the following (each circle represents a user, the pink lines represent a direct connection between these 2 users and the red circle represents a blocked user):



The number of users N in this image is 14, they are numbered from 0 to N - 1. You are always considered the user number 0. So here are some degrees between you and some other users:

  • The degree between you and user number 2 is 1 (you have direct connection).
  • The degree between you and user number 5 is 2 (the shortest way is to go through user 2, not through users 1 and 4).
  • The degree between you and user number 7 is 9 (there's another shorter path, but it must go through user 8 but user 8 is blocked).
Given the full list of connections, can you calculate the connection degree between you and all other users?


Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 100) representing the number of test cases. Followed by T test cases.

Each test case starts with a line containing 2 integers separated by a space, N (the number of users, the users will be numbered from 0 to N - 1, 2 ≤ N ≤ 1000) and M (the number of connections, 0 ≤ M ≤ 10000).

Followed by a line containing N - 1 integers separated by a space, each integer is either 0 or 1. The first number is for user number 1, the second number is for user number 2 and so on. If that number is 1, that means this user is blocked by you or they blocked you.

Followed by M lines, each line represents a connection. Each connection is described using 2 integers separated by a space, x and y (0 ≤ x < y < N), which means there's an accepted connection between x and y (the connections are bi-directional, which means if there's a connection between x and y, there's also a connection between y and x).

It's guaranteed that the same connection won't appear more than once.


Output Format:
For each test case print a single line containing N - 1 integers separated by a space, representing the connection degrees between you and all other users, the first number is for user number 1, the second number is for user number 2 and so on. If the user is blocked (by you or they blocked you) or if there's no way to reach that users using a valid path, print -1 for that user.


Sample Input:
3 6 4 0 0 1 0 0 0 1 1 2 2 4 1 4 5 6 0 0 0 0 0 1 0 2 0 4 2 3 1 3 2 4 7 7 0 0 1 0 0 0 0 1 0 2 1 2 2 3 3 4 3 5 4 6


Sample Output:
1 2 -1 2 -1 1 1 2 1 1 1 -1 -1 -1 -1


Notes:
Everything in this problem is just a story, that doesn't mean or confirm that any features is actually coming to WUZZUF.





Added by: ahmed_aly
Added at: 2017-10-09 20:00:00 UTC
Time Limit: 2 seconds
Partial score: No
Source:A2OJ Code Battle Round 1