A school building has n classrooms, numbered 0 to n - 1. At night, every room is locked except room 0. A guard wants to enter all the rooms. He can not enter a locked room without its key.
Some rooms have keys inside. Each key opens one room and has that room's number on it. When the guard enters a room, he takes all the keys there and can use them later.
The list rooms tells what is inside: rooms[i] is the list of keys in room i.
Return true if the guard can enter every room. Otherwise, return false.
Examples
Example 1:
Input: rooms = [[3],[],[1],[2]]
Output: true
Explanation: Room 0 has key 3. Room 3 has key 2. Room 2 has key 1. With key 1 the guard enters room 1. All 4 rooms are visited.
Example 2:
Input: rooms = [[1],[0,2],[1],[0]]
Output: false
Explanation: The guard can enter rooms 0, 1 and 2. But no room has key 3, so room 3 stays locked.
Example 3:
Input: rooms = [[2,3],[],[1],[0,2]]
Output: true
Explanation: Room 0 gives keys 2 and 3. Room 2 gives key 1. So the guard enters rooms 0, 2, 3 and 1.