Keys and Rooms

There are n rooms labeled 0 to n-1. Room 0 is unlocked. Each room contains a list of keys to other rooms. Given the list of keys in each room, print true if you can visit every room, false otherwise.

Example

Input (rooms, one key-list per line, - for empty):

(room 0 has key to room 1, room 1 has key to room 2, room 2 has key to room 3, room 3 has no keys) Output: true

Approach

This is graph reachability from a start node — BFS (or DFS) from room 0, following keys as directed edges, marking visited rooms. If every room ends up visited, you can reach them all.

Input format

Line 1: number of rooms N Next N lines: space-separated keys in that room, or - if none