#C4556. Taco Match Scheduling

    ID: 48107 Type: Default 1000ms 256MiB

Taco Match Scheduling

Taco Match Scheduling

You are given P players and M matches. Each player has a list of matches during which they are available to play. Your task is to determine whether it is possible to schedule at least one match for every player. In other words, you need to check if each player has at least one available match.

If every player has at least one available match, output Possible; otherwise, output Not Possible.

Note: The match IDs provided in the input do not need to be consecutive or within any particular range. The only requirement is that a player's availability list is non-empty.

Mathematically, for each player i (where 1 ≤ i ≤ P), let Ai be the set of matches available. The answer is "Possible" if and only if

[ \forall i \in {1,2,\ldots,P}, \quad |A_i| > 0. ]

Otherwise, the answer is "Not Possible".

inputFormat

The first line contains two space-separated integers: P (the number of players) and M (the number of matches). This is followed by P lines, each describing a player's availability. Each of these lines starts with an integer k (the number of available matches for that player), followed by k space-separated integers representing the match IDs.

outputFormat

Output a single line: Possible if every player has at least one available match, and Not Possible otherwise.## sample

3 3
2 1 2
1 3
2 2 3
Possible